Homework 2 (assigned October 6, due October 12; Revised)

Reading: CLRS chapters 6 and 7. Reading for next week's lecture: CLRS chapter 15, sections 15.1–15.4.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.
Note: You are responsible for the material covered in both "Do" exercises and assigned problems.
Note: If you work with others, indicate their names at the top of your homework paper. Everyone must submit their own independently written solutions.

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

1. Problem 7-1, parts a–e on pages 185–186.

2. Problem 7-2, parts a–d on pages 188–189.

3. Exercise 6.2-1 and 6.2-2 on page 156.

4. Exercise 6.5-1 and 6.5-2 on pages 164–165.

Assigned Problems (to be handed in):

Important: When describing an algorithm in pseudocode, explain the meaning of your variables in English. Comment the lines of your pseudocode. Your pseudocode should be short, clear, and complete to receive full credit. If your code is long, difficult to read, or incomplete, you will not receive full credit.

1. We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is "nearly" sorted. Upon calling quicksort on a subarray of fewer than k elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process.
   • Write pseudocode for this modified version of quicksort. (5 points)
   • Argue that this algorithm runs in O(nk + nlg(n/k)) expected time. (4 points)
   • How should we choose the cutoff k, in theory and then in practice? (1 point)

2. Suppose an array A consists of n elements, each of which is green, white, or orange. We wish to sort the elements so that all the greens come before all the whites, which come before all the oranges. The only operations permitted on the keys are the following.
   examine(A, i): report the color of the ith element of A.
   exchange(A, i, j): exchange the ith element of A with the jth element.
   Give a correct O(n) algorithm for green-white-orange sorting. Your algorithm must be in-place, meaning you cannot allocate another array to temporarily hold the items. No credit will be given for algorithms that are not O(n).
   • Describe your algorithm in pseudocode. (10 points)
   • Give a careful analysis of your algorithm that justifies its O(n) time complexity. (2 points)

3. There are two principal alteratives for constructing a max-heap from a given set of keys. The first is a bottom-up construction algorithm given by the following pseudocode (cf. page 157):
   BUILD-MAX-HEAP(A[1..n]))
   01 heapsize[A] = n
   02 for i = floor(n/2) downto 1
   03         MAX-HEAPIFY(A, i)
   The alternative algorithm constructs a max-heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. It is given by the following pseudocode:
   BUILD-MAX-HEAP′(A[1..n]))
   01 heapsize[A] = 1
   02 for i = 2 to n
   03         MAX-HEAP-INSERT(A, A[i])
   • Do the two procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP′ always yield the same heap when run on the same input array? Either prove that they do or provide a counterexample. (5 points)
   • Show that in the worst-case BUILD-MAX-HEAP′ requires Θ(n log n) time to build an n-element heap, i.e., show that BUILD-MAX-HEAP′ is both O(n log n) and Ω(n log n) in the worst case. (5 points)

4. Let A be a min-heap and i the index of a node in A. We change the key of the element A[i] to newkey, where the new value is less than the old value.
   • Write pseudocode for a procedure to restore the min-heap structure. (5 points)
   • Estimate the number of comparisons made by your algorithm as a function of n, the number of items in the heap. (3 points)

5. In class we considered binary heaps, where each node has at most two children. A d-ary heap is a heap in which each nonleaf node (except perhaps one) has exactly d children.
   • Suppose we implement a d-ary heap using an array A, similar to how we implement binary heaps: i.e., the root is contained in A[1], its children are contained in A[2…d+1], and so on. How do we implement PARENT(i), which computes the index of the parent of the ith node, for a d-ary heap? Write pseudocode. (2 points)
   • Since the nodes in a d-ary heap may have more than two children, LEFT(i) and RIGHT(i) are no longer sufficient to compute the indices of the children of the ith node. How do we implement the CHILD(i, k) function, which computes the index of the kth child of the ith node? Write pseudocode. (2 points)
   • Express the height of a d-ary heap containing n elements in terms of n and d. (1 point)
   • Write pseudocode for a generic "bubble down" (heapify-down) procedure for a d-ary max-heap containing n elements (8 points). Analyze the running time of your algorithm in terms of d and n (2 points).
   • Write pseudocode for a generic "bubble up" (heapify-up) procedure for a d-ary max-heap containing n elements (8 points). Analyze the running time of your algorithm in terms of d and n (2 points).
   • Complete the following table. Indicate which of your generic d-ary heap procedures (bubble-up or bubble-down), if any, the given procedure uses. (5 points)

     d-ary heap procedure	asymptotic running time	generic procedure used
     max-heapify
     build-max-heap
     extract-max
     insert
     increase-key