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). This was the exponent of n in the performance of Strassen's algorithm to multiply matrices, a divide and conquer strategy based on multiplying 2-by-2 matrices with 7 scalar multiplications. Starting with the recurrence T(n) = 7 * T(n / 2) + Θ(n²) the Master Method yields performanc of Θ(n^log₂(7)) = Θ(n^2.807355)

   ---

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 Θ. The worst-case performance is Θ(n²), which occurs for example when you sort an array already in increasing sorted order. In this case the right hand partition is always empty, and the new pivot is always at the right end of the old partition.

   ---

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? The two functions were the square root and division (specifically calculating the reciprocal). Once these algorithms get close to the solution, they provide twice as many digits of the answer at each iteration.

   ---

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

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

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

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

   ---

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.] We would use this result to design a divide-and-conquer algorithm using 68-by-68 matrices as the base. The next larger matrices to work with would be 68²-by-68² = 4624-by-4623. Next would come 68³-by-68³ = 314432-by-314432, so these numbers get large very fast. The recurrence for this algorithm is T(n) = 132464 * T(n / 68) + Θ(n²). Here, use the Master Method, a = 132464 and b = 68, so log₆₈(132464) has value log(132454) / log(68) = 5.1221 / 1.8325 = 2.79513. Thus the recurrence has solution Θ(n^2.79513), which is better than the Θ(n^2.807355) of Strassen's method. (This is a real result by Pan, although the algorithm is of no conceivable practical value.)

   ---

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]. [Misprint here: should be B[0], ..., B[74].] 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.

   The red code below shows a trial of the method in part (i) above, while the green code below shows a trial of the method in part (ii). The problem in part (i) is that we end up with duplicates, which were not wanted. Part (ii) is one way to avoid duplicates. (An acceptable answer to part (ii) need only describe the algorithm roughly, not necessarily with code.)

   You could use the basic idea of part (i) by (say) inserting each new item into a binary search tree, and just not inserting duplicates. However, you get quite a few duplicates. This method would turn particularly bad if you were (say) searching for 99 out of a 100, although in case you wanted more than 50 out of 100, you could decide on a collection to leave out. There are probably other ways to do this. [In fact, Mr. Tajchman gave a different clever answer, not using my C array. Mr. Wachter used essentially the same method.]

public class RandomSelect {

   static void insertWrong(double[] A, double[] B) {
      for (int i = 0; i < B.length; i++) {
         // rand(a,b) returns rand int r, a <= r <= b
         B[i] = A[rand(0,99)];
      }
   }

   static void randomize(int C[]) {
      int i;
      for (i = 0; i < C.length - 1; i++)
         exchange(C, i, rand(i,C.length - 1));
   }

   static void exchange(int C[], int i, int j) {
      int itemp = C[i];
      C[i] = C[j];
      C[j] = itemp;
   }

   static void insertRight(double[] A, double[] B) {
      int[] C = new int[100];
      for (int i = 0; i < C.length; i++)
         C[i] = i;
      randomize(C);
      for (int i = 0; i < B.length; i++)
         B[i] = A[C[i]];
   }

   static void insertRight2(double[] A, double[] B) {
      for (int i = 0; i < B.length; i++) {
         int index = rand(0, 99-i);
         B[i] = A[index];
         double temp = A[index];
         A[index] = A[99-i];
         A[99-i] = temp;
      }
   }

   static int rand(int a, int b) {
      return (int)((b - a + 1)*Math.random() + a);
   }

   static void sort(double[] X) {
      for (int i = 0; i < X.length - 1; i++)
         for (int j = 0; j < X.length - 1; j++)
            if (X[j] > X[j+1])
               exchange(X, j, j+1);
   }

   static void exchange(double X[],int i,int j){
      double temp = X[i];
      X[i] = X[j];
      X[j] = temp;
   }

   static void printit(double[] X) {
      for (int i = 0; i < X.length; i++) {
         System.out.print(X[i] + " ");
         if (i%10 == 9) System.out.println();
      }
      System.out.println();
   }

   public static void main(String[] args) {
      double[] A = new double[100];
      // put 100 distinct doubles into A somehow
      for (int i = 0; i < A.length; i++)
         A[i] = i + 0.5;
      double[] B = new double[75];
      System.out.println("75 distinct from A");
      System.out.println("Wrong way");
      insertWrong(A, B);
      sort(B);
      printit(B);
      System.out.println("Right way");
      insertRight(A, B);
      sort(B);
      printit(B);
      System.out.println("Second Right way");
      System.out.println("Tajchman, Wachter");
      insertRight2(A, B);
      sort(B);
      printit(B);
   }
}

75 values from A, 50 distinct
Wrong way (red or blue = duplicates)
 0.5  2.5  2.5  3.5  5.5  5.5  9.5  9.5  9.5 10.5 
13.5 13.5 14.5 14.5 15.5 18.5 18.5 22.5 25.5 25.5 
27.5 27.5 27.5 29.5 31.5 32.5 33.5 35.5 35.5 37.5 
39.5 39.5 45.5 45.5 46.5 46.5 46.5 47.5 48.5 49.5 
49.5 52.5 53.5 55.5 57.5 58.5 58.5 58.5 58.5 60.5 
61.5 62.5 62.5 65.5 69.5 70.5 70.5 70.5 73.5 73.5 
75.5 75.5 76.5 77.5 78.5 78.5 79.5 81.5 83.5 85.5 
89.5 92.5 93.5 97.5 98.5 

Right way
 0.5  1.5  2.5  3.5  5.5  6.5  7.5  8.5 10.5 11.5 
13.5 14.5 16.5 18.5 19.5 21.5 22.5 23.5 24.5 25.5 
26.5 27.5 28.5 29.5 30.5 31.5 32.5 33.5 34.5 35.5 
36.5 37.5 38.5 39.5 43.5 44.5 46.5 48.5 49.5 50.5 
52.5 54.5 57.5 59.5 60.5 61.5 62.5 63.5 64.5 65.5 
66.5 67.5 68.5 69.5 70.5 71.5 72.5 73.5 74.5 75.5 
76.5 77.5 79.5 80.5 82.5 83.5 84.5 85.5 86.5 87.5 
88.5 89.5 90.5 96.5 97.5 
Second Right way
Tajchman, Wachter
0.5 1.5 2.5 3.5 5.5 6.5 7.5 8.5 9.5 10.5 
11.5 12.5 13.5 14.5 17.5 18.5 19.5 20.5 21.5 22.5 
24.5 28.5 31.5 32.5 33.5 34.5 35.5 36.5 38.5 40.5 
41.5 42.5 43.5 44.5 45.5 46.5 47.5 48.5 49.5 50.5 
51.5 52.5 53.5 54.5 55.5 58.5 60.5 61.5 62.5 64.5 
65.5 67.5 68.5 70.5 71.5 72.5 76.5 77.5 78.5 79.5 
80.5 81.5 82.5 83.5 84.5 85.5 86.5 87.5 88.5 91.5 
92.5 95.5 96.5 97.5 99.5 

8. (10) Is an array in reverse sorted order (all values strictly decreasing) always a max-heap? Yes, because for a given row of the heap, each element is greater than or equal to each element on the row below. This means that each node has to have a value >= each of its children (if any).

   ---

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. In each case the red numbered items are the ones changed in going from the previous step.

   12 / \ 5 8 / \ / 2 10 14

   MaxHeapified at 3 12 / \ 5 14 / \ / 2 10 8

   MaxHeapified at 2 12 / \ 10 14 / \ / 2 5 8

   MaxHeapified at 1 14 / \ 10 12 / \ / 2 5 8

   ---

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.

       5 inserted 12 / 5

       8 inserted 12 / \ 5 8

       2 inserted 12 / \ 5 8 / 2

       10 inserted 12 / \ 5 8 / \ 2 10

       Restore heap 12 / \ 10 8 / \ 2 5

       14 inserted 12 / \ 10 8 / \ / 2 5 14

       Restore heap 12 / \ 10 14 / \ / 2 5 8

       Restore heap 14 / \ 10 12 / \ / 2 5 8

    2. Compare this result with the one in Question 9 above. Hey, they're the same, exactly the same. Even the exchanges made are the same.

    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.What is surprising is to have an example where they are the same. The heaps come out different for as simple as example as A = {1,2,3}, where the standard way gives {3,2,1} and the new way in this problem gives {3,1,2}. Here's a more complicated example, first in the standard way, and then using the method of this question. The resulting heaps are quite different.

       1
     /    \
    2      3
   / \    / 
  4   5   6

MaxHeapified at 3
       1
     /    \
    2      6
   / \    / 
  4   5   3

MaxHeapified at 2
       1
     /    \
    5      6
   / \    / 
  4   2   3

Start MaxHeapify at 1
       6
     /    \
    5      1
   / \    / 
  4   2   3

MaxHeapified at 1
       6
     /    \
    5      3
   / \    / 
  4   2   1

2 inserted
       1
     /
    2

Heap restored
       2
     /
    1

3 inserted
       2
     /   \
    1     3

Heap restored
       3
     /   \
    1     2

4 inserted
       3
     /   \
    1     2
   / 
  4

Start Restore
       3
     /   \
   4      2
   / 
  1

Heap restored
       4
     /    \
    3      2
   / 
  1

5 inserted
       4
     /   \
    3     2   
   / \ 
  1   5

Start restore
       4
     /   \
    5     2   
   / \ 
  1   3

Heap restored
       5
     /   \
    4     2   
   / \ 
  1   3

6 inserted
        5
     /    \
    4      2   
   / \    /
  1   3  6

Start restore
        5
     /    \
    4      6  
   / \    /
  1   3  2

Heap restored
        6
     /    \
    4      5   
   / \    /
  1   3  2