1. Consider the numbers 23, 18, 12, 14, 9, 7, 10, 6, 5, 8 in successive locations A[1], A[2], ..., A[10] of an array A.
   1. Write the array and its numbers as a complete binary tree as is done for heaps. Explain carefully why these numbers already form a heap.

      
                                    23
                                   /  \
                                  /    \
                                 /      \
                                /        \
                              18          12
                             /  \        /  \
                            /    \      /    \
                          14      9    7     10
                         /  \    /
                        6    5  8
                        
      Just check that every node is >= its left and right child.
      

   2. Carry out the first two steps of the heapsort algorithm on these numbers, that is, produce two numbers in the proper final locations and restore the heap property for the remaining numbers each time. Be careful to show all your work in a readable form.

   
      After first step.
     (changed = green)           18
                                /  \
                               /    \
                              /      \
                             /        \
                           14          12
                          /  \        /  \
                         /    \      /    \
                        8      9    7     10
                       / \
                      6   5    23
                     
   
      After second step.
      (changed = green)          14
                                /  \
                               /    \
                              /      \
                             /        \
                            9          12
                           / \        /  \
                          /   \      /    \
                         8     5    7     10
                        /       
                       6     18    23
                     
   

2. Using the same 10 numbers as in the previous problem, show how to insert the number 20 into this heap as a new entry. You must restore the heap property and show the resulting heap of 11 numbers.

   
                                 23
                                /  \
                               /    \
                              /      \
                             /        \
                           20          12
                          /  \        /  \
                         /    \      /    \
                       14     18    7     10
                      /  \    / \
                     6    5  8   9
                     
   After inserting 20 and restoring heap property. (green = changed)
   

The Master Theorem:

Suppose a, b, and c are constants in a recurrence of the form:

T(1) = c, for c > 0
T(n) = a*T(n/b) + f(n), for n = bk, k = 1, 2, ...

Suppose f(n) is in Big-Theta(n^d), where d >= 0 is a constant. Then the recurrence T(n) has the solution

T(n) is in Big-Theta(nd), if a < bd
T(n) is in Big-Theta(nd log(n)), if a = bd
T(n) is in Big-Theta(nlogba), if a > bd

3. In each case use the Master Theorem to find the Big-Theta order of the solution to the recurrence:

   
   T(n) = 2 * T(n/2) + n3
   Here a = 2, b = 2, d = 3, so 2 = a < b^d = 2^3 = 8
   and T(n) is in Big-Theta(n^3)
   T(n) = 4 * T(n/2) + n2
   Here a = 4, b = 2, d = 2, so 4 = a = b^d = 2^2 = 4
   and T(n) is in Big-Theta(n^2*log(n))
   

Consider the recurrence equations:

T(1) = 1
T(n) = 4 * T(n/2) + n

4. Use the Master Theorem to find the order of the solution.

   
   Here a = 4, b = 2, d = 1, so 4 = a > b^d = 2^1 = 2
   and T(n) is in Big-Theta(n^(log24) = Big-Theta(n^2)
   

5. Knowing the order, you could eventually guess the solution -- it is: T(n) = 2*n² - n. Prove using mathematical induction that this is the solution.

   
       Basis: For n = 1, T(1) = 1 by definition, but the formula gives
          T(1) = 2*12 - 1 = 2*1 - 1 = 1.  Check.
       
       Assume that T(k) = 2*k2 - k, for some k = 1, 2, 4, ...
       To show: T(2*k) = 2*(2*k)2 - 2*k = 8*k2 - 2*k
       
       Proof: T(2*k) = 4*T(k) + 2*k
                     = 4*(2*k2 - k) + 2*k
                     = 8*k2 - 4*k + 2*k
                     = 8*k2 - 2*k
   

6. One recitation problem was concerned with matching up n bolts of different sizes with n nuts. This problem turns out to have a solution very similar to another algorithm that we studied.
   1. What is the other algorithm?
   2. What is the Big-Theta average performance of these algorithms?
   3. The nut and bolt algorithm started out by choosing a nut or a bolt at random. What does this correspond to in the other algorithm that we studied?

      
      The "other algorithm" is quicksort, which has average-case
      performance of Big-Theta(n log n).
      Picking a nut or bolt at random at the start of the nut and bolt
      algorithm is similar to picking a pivot value at random in quicksort.
      

7. Using the "ordinary" method for multiplying 4-by-4 matrices, how many multiplications of numbers will be needed? Give a reason for your answer, more than just that your answer is given by a formula.

   
   To produce each of the 16 terms in the product, you have to
   multiply a row of the first matrix times a column of the second,
   using 4 multiplications, or 4*16 = 64 altogether.
   

8. Use Strassen's method for multiplying matrices to see how many multiplications of numbers would be required to multiply 4-by-4 matrices in this case. [Hint: you must not only use Strassen's basic method, but also the divide-and-conquer strategy.] Give a reason for your answer. For full credit you must explain in some detail how Strassen's basic result allows one to multiply the 4-by-4 matrices using the number of multiplications that you indicate.

   
   Break the 2 4-by-4's to be multiplied each into 4 2-by-2's.
   Then the 4-by-4's can be multiplied by Strassen's method
   using 7 multiplications of 2-by-2's.  Each of these 7 multiplications
   can be done (again by Strassen's method) using 7 ordinary multiplications,
   or 7*7 = 49 ordinary multiplications altogether.
   

9. The Stirling numbers S(n, k) satisfy the following recurrence equations:

   
   S(n, 0) = 0, for all n >= 0
   S(n, n) = 1, for all n >= 0
   S(n, k) = (n-1)*S(n-1, k) + S(n-1, k-1), otherwise
   

   Here is a function to calculate these numbers:

   
   int stirling(int n, int k) {
      int s1, s2;
      if (k == 0) return 0;
      if (n == k) return 1;
      s1 = stirling(n-1, k);
      s2 = stirling(n-1, k-1);
      return (n-1)*s1 + s2;
   }
   

   Use the declaration int S[50][50]; and assume all the S values are initialized to -1. Add code to the function so that it will do a memoized computation.

   
   int stirling(int n, int k) {
      int s1, s2;
      if (k == 0) return 0;
      if (n == k) return 1;
      if ( S[n][k] >= 0 ) { /* answer already in S */
          return S[n][k];
      }
      s1 = stirling(n-1, k);
      S[n-1][k] = s1;
      s2 = stirling(n-1, k-1);
      S[n-1][ k-1] = s2;
      S[n][k] = (n-1)*s1 + s2;
      return (n-1)*s1 + s2;
   }
   

Consider the function below:

int f(int m, int n) { // m >= 0
   int i = m;
   int j = n;
   while (i > 0) {
      j = j + 2;
      i = i - 1;
   }
   return j;
}

10. Assume that m >= 0 initially. Use the method from class with its four separate steps to prove that this function will always return the value

    n + 2*m

    You should use

    j = n + 2*(m - i)

    as the loop invariant. (There will be little if any credit if you don't follow the 4-step method taught in class.)

    
    a. Prove that loop invariant is true initially. 
       Given that i = m and j = n, we want to
       show that j = n + 2*(m - i).
       Substituting gives n = n + 2(m - m) or n = n, which is true.
       
    b. Prove that after each execution of one iteration of the loop,
       the loop invariant is still true. 
       Assume that j = n + 2*(m - i) is true initially.
       Calculate new values j' and i' for j and i, using
       j' = j + 2 and i' = i - 1.
       Now we need to show that the loop invariant is true for the
       new values, that is, j' = n + 2*(m - i'), or we want
       to see if j + 2 = n + 2*(m - (i - 1)) is still true.
       This simplifies to j + 2 = n + 2*m - 2*i + 2 or just
       j = n + 2*(m - i), which we assumed was true.
       
    c. Prove that on termination, the equation for the loop invariant
       shows that the correct value is being calculated. 
       On termination, we must have i = 0 true.  Then the
       loop invariant formula: j = n + 2*(m - i) just becomes
       j = n + 2*(m - 0) = n + 2*m, which is what we needed to prove.
       
    d. Prove that the algorithm terminates. 
       Since we assume m >= 0, this means that i >= 0.
       If i == 0, the algorithm terminates without executing the loop.
       Otherwise, if i > 0, the inside of the while subtracts 1 from
       i at each iteration, so eventually the algorithm must terminate.