# COT 6405 – Introduction to Theory of Algorithms Assignment 2

\$30.00

Category:

## Description

5/5 - (1 vote)

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, 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

(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) +