CS 6515 EXAM 2 ACTUAL TEST PAPER QUESTIONS CORRECT ANSWERS GRADED A PLUS
Question:
master theorem.
Answer:
-if f(n) = O n^(logba -∈) for some const ∈>0 then T(n) =θn^(logb a) if f(n) =θn^(log b a ) then
T(n)=θn^(logba) logn if f(n) =Ω(n^logba + ε) for some constant ε>0 and if af(n/b) ≥ cf(n) for some
constant c<1 and all sufficiently large n, then T(n) = θf(n) f(n) dominates g(n) iff grows
polynomially faster than g(n). this is a stronger condition than f(n) = ωg(n) does not apply for the
gap between the tree cases (little o and little omega)
Question:
when master theorem does not apply.
Answer:
a must be >= 1, b must be >1 (they don't necessarily need to be integers) can check this by the limit
test and leaving the + ∈ and if there is not an ∈ you can pick to make it polynomially faster, then the
rule does not apply f(n) is negative ex. nlogn / n^1+e cuz both have n^1 in it if a = 2^n (cuz not
constant) if constant work is subtracted
Question:
polynomially larger? n^2 vs. n.
Answer:
yes
Question:
polynomially larger? n^2logn vs. n^2.
,Answer:
no
Question:
polynomially larger? n^3 log n vs. n^2.
Answer:
yes
Question:
polynomially larger? n^2.001 vs. n^2.
Answer:
yes
Question:
polynomially larger? nlogn vs. n^log4 3.
Answer:
yes
Question:
applying the master theorem given recurrences.
Answer:
coefficient is a, division is b and function is constant work compare n^logb a vs. f(n)
Question:
special rules for master theorem.
Answer:
,-case 2 only: this happens when log_b a is equal to the degree of n in f(n). if there is no log then
master method does not apply. if there is a log, look at the power. if the power of the log is > -1, then
T(n) = theta log _ b a * log^k+1 n where k is the power of the log if the power of the log = -1 then
T(n) = theta log_ b a log log n if the power of the log < -1 then T(n) = theta log_ b a
Question:
proof by induction on the binary search.
Answer:
base case: on the 0 iteration, x exists in A or x never existed in A at all inductive hypothesis: x exists
in A iff x lies in the subarray A[L.H] inductive step: if(A[mid] <= x) L<- mid else H<- mid-1 if
A[L] = x return L
Question:
heap sort.
Answer:
insert n inputs into the heap. call extractmin n times. values sorted least to greatest
Question:
merge sort.
Answer:
based on linear merge of 2 sorted arrays. divide and conquer algorithm
Question:
selection sort.
Answer:
goes thru and finds the smallest element and brings it to the front of the array
Question:
, running time of bubble sort.
Answer:
n^2
Question:
insertion sort running time.
Answer:
n^2
Question:
shell sort running time.
Answer:
n^2 or n^4/3 or n log^2n
Question:
quick sort running time.
Answer:
n log n
Question:
model of computation.
Answer:
what we can do in constant time. sorting algorithm can only do limited work in constant time. they
can make limited decisions about their inputs in constant time
Question:
limited decisions for sorting.
Question:
master theorem.
Answer:
-if f(n) = O n^(logba -∈) for some const ∈>0 then T(n) =θn^(logb a) if f(n) =θn^(log b a ) then
T(n)=θn^(logba) logn if f(n) =Ω(n^logba + ε) for some constant ε>0 and if af(n/b) ≥ cf(n) for some
constant c<1 and all sufficiently large n, then T(n) = θf(n) f(n) dominates g(n) iff grows
polynomially faster than g(n). this is a stronger condition than f(n) = ωg(n) does not apply for the
gap between the tree cases (little o and little omega)
Question:
when master theorem does not apply.
Answer:
a must be >= 1, b must be >1 (they don't necessarily need to be integers) can check this by the limit
test and leaving the + ∈ and if there is not an ∈ you can pick to make it polynomially faster, then the
rule does not apply f(n) is negative ex. nlogn / n^1+e cuz both have n^1 in it if a = 2^n (cuz not
constant) if constant work is subtracted
Question:
polynomially larger? n^2 vs. n.
Answer:
yes
Question:
polynomially larger? n^2logn vs. n^2.
,Answer:
no
Question:
polynomially larger? n^3 log n vs. n^2.
Answer:
yes
Question:
polynomially larger? n^2.001 vs. n^2.
Answer:
yes
Question:
polynomially larger? nlogn vs. n^log4 3.
Answer:
yes
Question:
applying the master theorem given recurrences.
Answer:
coefficient is a, division is b and function is constant work compare n^logb a vs. f(n)
Question:
special rules for master theorem.
Answer:
,-case 2 only: this happens when log_b a is equal to the degree of n in f(n). if there is no log then
master method does not apply. if there is a log, look at the power. if the power of the log is > -1, then
T(n) = theta log _ b a * log^k+1 n where k is the power of the log if the power of the log = -1 then
T(n) = theta log_ b a log log n if the power of the log < -1 then T(n) = theta log_ b a
Question:
proof by induction on the binary search.
Answer:
base case: on the 0 iteration, x exists in A or x never existed in A at all inductive hypothesis: x exists
in A iff x lies in the subarray A[L.H] inductive step: if(A[mid] <= x) L<- mid else H<- mid-1 if
A[L] = x return L
Question:
heap sort.
Answer:
insert n inputs into the heap. call extractmin n times. values sorted least to greatest
Question:
merge sort.
Answer:
based on linear merge of 2 sorted arrays. divide and conquer algorithm
Question:
selection sort.
Answer:
goes thru and finds the smallest element and brings it to the front of the array
Question:
, running time of bubble sort.
Answer:
n^2
Question:
insertion sort running time.
Answer:
n^2
Question:
shell sort running time.
Answer:
n^2 or n^4/3 or n log^2n
Question:
quick sort running time.
Answer:
n log n
Question:
model of computation.
Answer:
what we can do in constant time. sorting algorithm can only do limited work in constant time. they
can make limited decisions about their inputs in constant time
Question:
limited decisions for sorting.
