Assignment 2 (90 points)
1. (4 points each question) Use the Master Theory to solve the following
recurrences
a. T(n) = 3T(n/27) + 1
b. T(n) = 7T(n/8) + lgn
c. T(n) = 2T(n/4) + n
d. T(n) = 2T(n/4) + 𝑛
2
e. T(n) = 2T(n/4) +√𝑛 lgn
2. (10 points) Illustrate the operation of MAX-HEAPIFY (A, 1) on the array A = {27,
17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0}.
3. (10 points) (Textbook 6.4-1 page 160) Illustrate the operation of HEAPSORT on
the array A = {5, 13, 2, 25, 7, 17, 20, 8, 4}.
4. (10 points) Use the substitution method to prove that T(n) ∈ Ω(𝑛lg𝑛) for the
recurrence T(n) = 2T(0.5n - 3) + n. In your proof, please do not simply ignore the
constant to assume that T(0.5n - 3) is approximately equal to T(0.5n).
5. For HEAPSORT codes below
Heapsort(A)
{
Build-MAX-Heap(A);
for (i = A.length downto 2)
{
Swap(A[1], A[i]);
A.heap_size= A.heap_size - 1;
MAX-Heapify(A, 1);
}
}
(a) (3 points) What is the number of required swap operations when heapsort
the array A = {5, 13, 2, 25, 7, 17, 20, 8, 4}? Explain your reason.
(b) (3 points) If we replace MAX-Heapify(A, 1) with Build-MAX-Heap(A), what is
the number of required swap operations when heapsort the array A? Explain
your reason.
(c) (4 points) Does the asymptotic upper bound of Heapsort increase from
O(nlgn) to O(𝑛
2
)? Why? (Hint: compare the number of swap operations
before and after the change for the worst case).
6. (10 points) Can we use the Master Theory on the recurrence T(n) = 2T(n/2) +
sin(n)? Please answer YES or NO and then explain your reason. Can we use the
Master Theory on the recurrence T(n) = T(n/2) + nsin(n) + 2n? Please answer YES
or NO and then explain your reason.
7. (10 points) Use the recursion tree method to determine the asymptotic upper
and lower bounds for the recurrence T(n) = 2T (𝑛
2
+ 8) + n.
8. (10 points) Use mathematical induction to prove the correctness of the BuildMAX-Heap function.
