1. In terms of the master recurrence theorem, where does the equation T (n) = T
ID: 3583246 • Letter: 1
Question
1. In terms of the master recurrence theorem, where does the equation T (n) = T ( n ) + 1 fall? 4
(A) case 1
(B) case 3
(C) between case 1 and case 2
(D) between case 2 and case 3
(E) case 2
(F) the equation is not in the correct form
2. Using the master recurrence theorem, what is the solution of T (n) = 3T ( n ) + n
3 logn
?
(A) (nlogn)
(B) (n)
(C) the master theorem cannot be used
(D) ( n ) log n
(E) (logn)
3. Consider using the master recurrence theorem and the regularity condition for case 3 to solve the equation T(n) =
5T ( n ) + n2 . What is the smallest legal value of the constant c listed for the solution? The log (base 5) of 2 is ~ 0.431. 2
The log (base 2) of 5 is ~ 2.322.
(A) 0.3
(B) no legal value is listed (C) 0.1
(D) 0.2
(E) case 3 does not apply
4. Consider running the linear selection algorithm on an array with n = 13k unique elements. What is a reasonable recurrence equation to describe the running time of the algorithm? Assume the median of medians is found with groups of thirteen.
(A) T(n)=T(n )+T(12n)+(n) 13 13
(B) T(n)=T(n )+T(7n)+(n) 13 13
(C) T(n)=T(n )+T(19n)+(n) 13 26
(D) T(n)=T(n )+T(11n)+(n) 13 13
(E) nonearereasonable
(F) T(n)=T(n )+T(6n)+(n)
(G) T(n)=T(n )+T(7n)+(n) 13 26
(H) T(n)=T(n )+T(23n)+(n) 13 26
13 13
5. Consider running the linear selection algorithm on an array with n = 4k unique elements. What is a reasonable recurrence equation to describe the running time of the algorithm? Assume the median of medians is found with groups of four and that, after sorting a group of four, the second element (index 1) is chosen as the median of that group. Hint: you are looking for the worst case, so look at inding both the minimum number of values less than the median of medians and the minimum number of values greater than the median of medians to see which leads to the largest partition.
(A) T(n) = T(n)+T(n)+(n) (E) T(n) = T(n)+T(5n)+(n) 44 48
(B) T(n) = T(n)+T(2n)+(n) 44
(C) T(n) = T(n)+T(3n)+(n) 4 8
(D) T(n) = T(n)+T(7n)+(n) 48
(F) T(n) = T(n)+T(3n)+(n) 44
(G) none are reasonable
6. In an eicient decision tree (no unnecessary comparisons) for the comparison sorting of n numbers, what does the longest path from the root to a leaf represent?
(A) the average case behavior of the worst possible algo- rithm
(B) the best case behavior of the best possible algorithm
(C) the worst case behavior of the worst possible algo- rithm
(D) the average case behavior of the best possible algo- rithm
(E) the worst case behavior of the best possible algorithm
(F) nothing important, the shortest path is what’s impor- tant
(G) the best case behavior of the worst possible algorithm
7. Suppose you use log n buckets to bucket sort n numbers, uniformly distributed. What would be the expected running time of bucket sorting those numbers if you used mergesort sort to sort the individual buckets? Make sure you choose the choose the simplest form.
(A) the correct answer is not given
(B) (logn× n ×(lognloglogn))
(E) (n log n)
(F) ( n ×log n )
log n (C) ( n ×logn)
log n log n
(G) (logn× n ×log n )
log n (D) ( n
log n log n (H) (logn× n ×logn)
× (logn loglogn))
8. Consider using bucket sort to sort n numbers evenly distributed over the range 0 to m. Roughly, what size bucket should
log n you use?
log n
(A) m (C) n n
(B) n (D) m m
9. Consider a node n in a typical red-black tree and all paths from n to a leaf. Which of the following is a constraint on these trees?
(A) the number of red nodes on each path is the same (D) the number of nodes (red or black) on each path is
(B) the number of black nodes on each path is the same (C) each path must start with a black node
the same
10. Suppose one wished to allow more red nodes in a red-black tree, but still wished this new tree to have the same asymptotic behavior as before. One could allow more red nodes on any path to a leaf as long as:
(A) no red node could have a red sibling.
(B) the number of black nodes between any two red nodes is bounded by a constant.
(C) no black node could have a red parent.
(D) the number of red nodes between any two black nodes is bounded by a constant.
11. Consider an interior node with a two children, both leaves, in a red-black tree. Must that node have a sibling? If so, what is the maximum number of descendants that sibling can have?
(A) the node must have a sibling / 0 (B) the node must have a sibling / 30 (C) the correct answer is not listed (D) the node must have a sibling / 6
(E) the node must have a sibling / 2 (F) the node must have a sibling / 16
(G) the node may not have a sibling (H) the node must have a sibling / 14
12. Consider a dynamic illable array whose capacity C grows to 3C (integer division) when illed. Let S represent the 2
number of illed slots and E, the number of empty slots. Which potential function works for proving the amortized
cost of an insertion into a full array is a constant? If it is not possible to show an amortized constant cost, select “not
possible”. Hint: The actual cost of the insert is S + 1 and, after the insert, C = 3S and E = S 1, where S is the size
immediately before the insert. (A) 3SE
2
(B) not possible
(C) the correct answer is not listed (D) 3S2E
22
(E) 2S+2E (F) C + S
2
(G) C + 2E (H) C2S
Explanation / Answer
Answer
1.
(F)
The correct form of the Master Theorem is
T(n) = aT(n/b) + f(n)
where a>=1 and b>1 are constants and f(n) is an asymptotically positive function.
As the equation given in the qestion doesn't have a similar form, the option is (F)
2.
(C)
As the given equation dosen't match that of the Master theorem as explained earlier
3.
(E)
As in the given equation b = 1 which is not acceptable by the Master Theorem.
6.
(C)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.