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.

   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.

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.

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
   
   T(n) = 4 * T(n/2) + n2
   

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.

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.

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?

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.

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.

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.

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.)