## Description

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.