Non-Programming Exercises:

1. Start with an initial array A defined by int[] A = {0, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; Recall that we don't use the element A[0], and that there are 10 elements in the array: A[1], ..., A[10]. Carry out the function BuildMaxHeap(A) to convert this into a heap. (You must show your work, scratching through old values and putting in new ones. You must allow enough room so that it can be read.) [The answer in the array should be: int[] A = {0, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1};]

   ---

2. Apply the function Heapsort(A) by hand to the result of problem 1 above, to end up with elements A[1], ..., A[10] in increasing order. (Again, you must show your work, possibly using multiple diagrams so that it isn't too messy.)

   ---

3. Using the heap in problem 1 above, use the function HeapExtractMax(A) to remove one element. Then use the function MaxHeapInsert(A, 15) to insert a new item with value 15. Then insert another new item with value 12 using MaxHeapInsert(A, 12). Finally use the function HeapExtractMax(A) one more time to remove the maximum value. (We started with 10 items in the heap, removed 2 and added 2, so you should have 10 at the end.)

   ---

4. In the example of dynamic programming that solves the matrix chain multiplication problem, suppose the sequence of dimensions is: 5, 10, 3, 12, 5, 50, 6. (This means that M₁ is a [5-by-10], M₂ is a [10-by-3], ..., M₆ is a [50-by-6].) Run through the algorithm by hand to find the optimal parenthesization. (Refer to Feb 26.)

5. Use the memoization technique as well as a straight recursive technique to calculate values of the function:

    C(n, 0) = 1, for all n
    C(n, n) = 1, for all n
    C(n, k) = C(n-1, k-1) + C(n-1, k), for n > k and k > 0
   

   This example is on pages 277-278 of your text, but you are not to use the book's algorithm on page 278 (no credit for this) but you must use memoization as illustrated in the program Fibonacci numbers. As in this example, you should calculate without memoization, counting the number of recursive calls, and compute with memoization, counting the number of insertions into an array. In this case you will need to use a 2-dimensional array. Try this for n = 5, k = 3; n = 10, k = 6; n = 20, k = 10; n = 25, k = 14; n = 30, k = 15. [Partial answer: C(20, 10) = 184756.]

6. Let X(n) denote the number of ways to fully parenthesize a product of n matrices. Then show that X(n) satisfies the recurrence:

    X(1) = 1
    X(n) = Sum (X(i)*X(n-i)), where the sum goes for i from 1 to n-1
   

   (Note: earlier the formula above had a 1 where an i should have been.)

   It turns out that the formula for X(n) is:

    X(n + 1) = (1/(n+1)) C(2n, n),
   

   where this is the same C in the previous problem. Use the results of the previous problem to find X(11) and X(16). [Partial answer: X(11) = 16796.]