Directions: Do not spend too much time on any one problem. Try to give as short an answer as you can that still fully answers the question.

---

1. (10) Give the name of a significant example in this course where we encountered the number log₂(7).

    

   ---

2. (14) For your text's basic Quicksort algorithm, give the worst case performance, in terms of Θ. Give a specific example of an array for which the worst case is realized. Explain the simple alteration to the basic quicksort algorithm that guarantees an expected better performance. Give this expected better performance in terms of Θ.

    

   ---

3. (14) One of the weird topics showed how to use Newton's Method from calculus to compute two important functions. In each case this technique was actually used on real machines. What were these two functions? How fast was the convergence given by Newton's Method?

    

   ---

4. (28) In each case attempt to use the Master Theorem to find the Θ order of the solution to the recurrence:
   1. T(n) = 2 * T(n / 2) + n³

   2. T(n) = 4 * T(n / 2) + n²

   3. T(n) = 2 * T(n / 4) + n 

   4. T(n) = 3 * T(n / 27) + n³*log(n)

   5. T(n) = 9 * T(n / 3) + n³*log(n)

   ---

5. (24) 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;
   }
   

   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. (This is such a simple program that you can easily see what it does. But I'm testing your ability to follow a methodology. There will be little if any credit if you don't follow the 4-step method taught in class:

   1. Prove that loop invariant is true initially.

       

   2. Prove that after each execution of one iteration of the loop, the loop invariant is still true.

       

   3. Prove that on termination, the equation for the loop invariant shows that the correct value is being calculated.

       

   4. Prove that the algorithm terminates. )

    

   ---

6. (20) According to your text, V. Pan discovered a way of multiplying 68-by-68 matrices in 132464 scalar multiplications. Consider a divide-and-conquer strategy for multiplying matrices based on this discovery. Give the recurrence equation for such a divide-and-conquer algorithm. Give an expression for the Θ performance of this algorithm. (You don't need to use a calculator to work out the value of this expression.) [Hint: Don't let the big numbers intimidate you -- they're just numbers, and we've done problems similar to this before.]

    

   ---

7. (24) Suppose we have an array A holding 100 distinct elements, in locations A[0], ..., A[99]. We wish to pick 75 of these elements at random, with no repetitions, and place them in an array B, in locations B[0], ..., B[75]. At the end we should have 75 distinct elements in B, chosen at random from A.
   1. What is wrong with the following algorithm to do this:

      
      double[] A = new double[100];
      // put 100 distinct doubles into A somehow
      double[] B = new double[75];
      insert(A, B);
      
      void insert(double[] A, double[] B) {
         for (int i = 0; i < 75; i++) {
            // Random(a,b) returns random int between a and b inclusive
            B[i] = A[Random(0,99)];
         }
      }
      

       

   2. Let C be the array
      int [ ] C = {0,1,2,...,99}; // not legal Java

      Show how to use a randomization of C to solve the problem in (i) above efficiently.

    

    

   ---

8. (10) Is an array in reverse sorted order (all values strictly decreasing) always a max-heap?

    

    

   ---

9. (16)Suppose an array A has locations A[1], ..., A[6] equal to {12,5,8,2,10,14}. Show step-by-step the process of making this array into a max-heap.

    

    

   ---

10. (16) Suppose an array A has locations A[1], ..., A[9] equal to {25,13,20,8,7,17,2,5,4}. This is a max-heap. As one of the 2 steps of a priority queue, show step-by-step the process of removing the maximum element and restoring the heap property. (Just remove one element, and stop.)

     

     

    ---

11. (24) There is a completely different way to start with an array of numbers and create a max-heap out of them. Given A with locations A[1],...,A[A.length], consider the function, in your text's notation:

    
    BuildMaxHeap2(A)
       a.heapsize = 1
       for i = 2 to A.length
          MaxHeapInsert(A, A[i])
    

    1. Try this new function out on the same array A as in Question 9 above, with locations A[1], ..., A[6] equal to {12,5,8,2,10,14}. Show the process step-by-step and the end result.

        

    2. Compare this result with the one in Question 9 above.

        

    3. (Bonus question, do this last) Do these two functions always create exactly the same heap when run on exactly the same input array? Give a proof or a counter-example.