CS 3343/3341 Spring 2004
Assignment 7
Answers

  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.)
    Answer: 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.)
    Answer: Successive steps in the answer, with remaining heap in bold orange:

  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.)
    Answer:
    
{16, 14, 10, 8, 7, 9, 3, 2, 4, 1};     // initial
{14,  8, 10, 4, 7, 9, 3, 2, 1};        // after extracting max (16) and restoring heap
{15, 14, 10, 4, 8, 9, 3, 2, 1, 7};     // after inserting 15 and restoring heap
{15, 14, 10, 4,12, 9, 3, 2, 1, 7, 12}; // after inserting 12 and restoring heap
{14, 12, 10, 4, 8, 9, 3, 2, 1, 7};     // after extracting max (15) and restoring heap

  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 M1 is a [5-by-10], M2 is a [10-by-3], ..., M6 is a [50-by-6].) Run through the algorithm by hand to find the optimal parenthesization. (Refer to Feb 26.)
    Answer:
    Here is the table, just like the one in in the online pages:

    Here are the calculations:

    As a check, here is the output of my C program that calculates this stuff (the output is arranged slightly differently):

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

    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.]
    Answer:
    A program using memoization to calculate C is here: Comb.c. Here is a log of output (edited):

  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:

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

    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.]
    Answer:
    Consider the initial values for X(n):

    This shows why the summation formula for X(n) is correct, since on needs to locate the point of the last multiplication in the sequence, and that leads to two smaller values of X. Finally, here are values for X(n), where 1 <= n <= 17