Homework 3 (assigned April 16, due April 22)

Reading: Review CLRS chapter 6; read CLRS chapters 8 and 9.

Written assignment: Solve the following "Do" exercises and assigned problems. Turn in only the problem solutions. Please note: You are responsible for the material covered in both "Do" exercises and problems.

"Do" Exercises (not to be handed in):

1. Use the iteration method to solve the recurrence
         T(n) = 3T(n/2) + n for n > 1,   T(1) = 1.
2. Use the substitution method to prove that the recurrence
         T(n) = T(n/2) + n for n > 1,   T(1) = 1
   has an asymptotically tight bound T(n) = Θ(n).
3. Use the substitution method to prove that the recurrence
         T(n) = 4T(n/2) + n for n > 1, T(1) = 1
   has an upper bound T(n) = O(n²).

Problems (to be handed in):

1. Building heaps
   
   1. Using the pseudocode on CLRS page 133, construct a heap for the array A = [1, 8, 6, 5, 3, 7, 4]. (5 points)
   2. Using the pseudocode on CLRS page 142, construct a heap for the array A = [1, 8, 6, 5, 3, 7, 4]. (5 points)
   3. Do these two algorithms (bottom-up and top-down build-heap algorithms) always yield the same heap when run on the same input array? Either prove that they do or provide a counterexample. (5 points)
   4. Using the pseudocode on CLRS page 136, show how heapsort sorts the array A = [1, 8, 6, 5, 3, 7, 4]. (5 points)

2. Heap-Delete
   The operation Heap-Delete(A, i) deletes the item in node i from heap A. Give an implementation of Heap-Delete that runs in O(lg n) time for an n-element max-heap. Write pseudocode for your algorithm and justify its running time. You may use any of the procedures for the heap operations given in CLRS chapter 6. (10 points)

3. Merging k sorted lists
   Describe an O(n lg k)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. Analyze the running time of your algorithm. (15 points)
   Hint: Use a max-heap.

4. Algorithm design
   Given a positive integer n, find a positive integer r such that r² = n, if such an r exists. Describe an algorithm to solve this problem. Make your algorithm as efficient as possible. Write pseudocode for your algorithm and analyze its running time. (15 points)
   Hint: Use binary search.