(Textbook. Click for information.)

CS 3343/3341  Analysis of Algorithms  Spring 2012  Recitation 8  Exam Review     Partial Answers

Note: I did not include answers to questons 10, 11, 12, 13 (the stuff on heaps and priority queues) or to question 14 (the Master Theorem), but you already have lots of example answers to these. If you have particular questions, you should email me.

• Fibonacci matrix identity: Rec 4, Question 1,
• Fibonacci sum identity: Rec 6, Question 5

Not on this review exam.

• Standard (Slow) Exponentiation: Rec 1, Question 4,
• Multiplication: Rec 4, Question 3, and
• Quick Exponentiation: Rec 4, Question 3.

1. Carry out the proof asked for in the table below:

   Consider the following function that will calculate the quotient and remainder of its two input parameters. (It does with this without using an actual "divide", but just with addition and subtraction.) The inputs are:    n >= 0 (the "dividend") and    d >= 1 (the "divisor"). The algorithm calculates and returns:    q >= 0 (the "quotient") and    d >= 1 (the "divisor").    r (the "remainder"), such that on termination, the following are true:    r >= 0,    r < d, and    n = d * q + r.

   Here is the picture: q +------- d | n -----+ ------- r Here is the function: // div: inputs n >= 0 and d >= 1 // returns the pair (q, r) (int, int) div(int n, int d) { int q = 0, r = n; while (r >= d) { q = q + 1; r = r - d; } return (q, r); } The loop invariant is:    n = d * q + r Carefully write out all four steps in the proof.

   Initially: n >= 0, d >= 1, q = 0, r = n, so d*q + r = d*0 + n = n, and the loop invariant is true. Loop invariant remains true: Suppose the loop invariant is true at the start of the loop. At the end of a loop iteration, let q' = q + 1 and r' = r - d be the new values for q and r. Then d*q' + r' = d*(q + 1) + (r - d) = d*q + d + r - d = d*q + r = n, so the loop invariant is true for the new values of q and r. After the loop terminates: The three required properties (in red) are true. We must have !(r >= d), i.e., r < d, or it wouldn't terminate. The loop invariant is still true, that is: n = d * q + r. On the last loop iteration, at the start we have r >= d, and yet at the end we have r' = r - d >= d - d = 0, so at termination, r >= 0. Termination: Start with r >= 0 (since it is set to n) and d >= 1. Keep subtracting d from r and eventually we must get r < d. Notice that, given inputs n and d, if the program produces outputs q and r satisfying the conditions in red above, this is the very definition of division.

2. We studied to algorithms for raising an integer to an integer power: a slow algorithm and a fast one. Consider the algorithms as raising a fixed a to a power n, so that we have two function expslow(n), and expfast(n), each calculating aⁿ.
   1. Give the Θ bounds on the performance of each of these two algorithms. [Slow: Θ(n), Fast: Θ(log(n)).]

   2. In one of the weird topics, we found a special application for the fast exponentiation. What was it? [This allowed calculation of the nth Fibonacci number F_n in time Θ(log(n)).]

3. 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 Θ. [Quicksort has worst case performance of Θ(n²), which the basic form of quicksort encounters by sorting an array already in sorted order. All one has to do is pick the pivot at random at each stage in order to ensure an expected sort time of Θ(n log(n)).]

4. [Oops! This is just intro material, and not a question. Just leave #4 blank.] Consider the following algorithm that we studied in class:
   // A is an array with n elements, indexed by 0 to n-1 inclusive

   void randomize(int[] A) {
      for (int i = 0; i < n-1; i++) {
         int r = randomInt(i, n-1); // i to n-1 inclusive
         interchange(A[i], A[r]); // possibly i == r
      }
   }

   (Here randomInt(a, b) returns a true random integer r, satisfying a <= r <= b such that each of the integers between a and b (inclusive) is equally likely to occur.)

5. Trace through the execution of this function, showing the result after each loop iteration, using as input the array of integers A = {6,7,8,9}, so that n == 4. Assume the function randomInt returns 2, 1, and 3 the three times it is called.

   i	r	Action	A={6,7,8,9}
   0	2	Inter(0,2)	A={8,7,6,9}
   1	1	Inter(1,1)	A={8,7,6,9}
   2	3	Inter(2,3)	A={8,7,9,6}
   4	3	Inter(3,3)	A={8,7,9,6}

6. Say in detail what happens if the loop is written
   for (int i = 0; i < n; i++)

   with "n" instead of "n-1". (You must say much more than just that "there is another loop iteration.") [The extra iteration is shown at the end of the table above. In this case randomInt(3,3) returns the best random in between 3 and 3 that it can, namely 3.]

7. What does this function do, and what did we use it for in the course? [This function is an efficient way to rearrange an array into random order.]

• Divide and Conquer: Ordinary matrix multiplication: Matrix Multiplication.
• Strassen's matrix multiplication: Strassen's Matrix Multiplication.
• Strassen's Matrix Multiplication: Theory: Strassen's Theory.
• Multiplying 3-by-3 matrices: Recitation 6: Questions 6, 7, 8.

8. Consider the matrix multiplication of 4-by-4 matrices.
   1. Using the ordinary method of matrix multiplication, how many scalar multiplications are required? Don't just state this number, but calculate the number from the ordinary matrix multiplication algorithm, where each element of the answer is the inner product of a length 4 row times a length 4 column. [Each inner product takes 4 mults, and there are 4*4 = 16 such, so there are 4*4*4 = 64 mults altogether.]
   2. Using the divide-and-conquer approach and Strassen's method of multiplying 2-by-2 matrices, how many scaler multiplications would be required? Again justify your answer. [Regarding the 4-by-4 matrices as 2-by-2 matrices of 2-by-2 matrices, at the top level, Strassen's method would take 7 mults of 2-by-2 matrices, and each of these would take 7 scalar mults, so there would be 7*7 = 49 scalar mults altogether.]

9. Now consider 5-by-5 matrices. Again how many scalar multiplications would be required using ordinary matrix multiplication? (Just a number for the answer.) [5³ = 125.] Suppose one could multiply 5-by-5 matrices using 91 scalar multiplications. Give the recurrence for a divide-and-conquer algorithm based on this supposition. Use the Master Method (or some other approach) so get the asymptotic performance in this case. Would this be an interesting result? [The recurrence in this case would be T(n) = 91 T(n/5) + Θ(n²). The Master Method gives performance of Θ(n^log₅(91)) = Θ(n^2.8027545). Because this is better than Strassen's method at Θ(n^log₂(7)) = Θ(n^2.8073549), it would definitely be of interest. (Notice how close these two are.)]

• Discussion and algorithms, including for heapsort and for a priority queue: Heaps.
• Examples using diagrams of the heap at each stage:
  • Building a heap from an array in random order: Building a heap.
  • Running heapsort from an array in random order: Heapsort.
  • Repeatedly extracting the maximum from a heap: Extract Maximum.
  • Repeatedly inserting a new element into a heap: Inserting Into a Heap.
• Heapsort implementation and test: Implementation and test of heapsort.
• Priority Queue implementation and test: Implementation and test of a priority queue.
• Examples in Recreation 5: Heap examples.
• Examples in Recreation 6: Priority Queue examples.

10. Suppose an array A has locations A[1], ..., A[9] equal to {5,13,2,25,7,17,20,8,4}. Show step-by-step the process of making this array into a heap.

11. 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. Show just the first two steps of the progress of heapsort on this array, starting to sort it into increasing order. At each of the two steps indicate also the value of heapsize.

12. Suppose an array A has locations A[1], ..., A[11] equal to {20,16,8,14,11,7,4,10,12,6,3}. 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.

13. Suppose an array A has locations A[1], ..., A[10] equal to {18,15,9,11,10,6,2,8,1,7}. This is a max-heap. As one of the 2 steps of a priority queue, show step-by-step the process of inserting the element 16 into this heap and restoring the heap property. (This uses the Heap-Increase-Key function.)

• Merge Sort: Recursion Tree for Merge Sort,
• Quicksort: Recursion Tree Unbalanced Quick Sort, and
• Medians: Median of an Array, Question 6

Not on this review exam.

• Master Method, and
• Rec 6: Recurrences (Question 1).

14. Attempt to use the Master Method to solve each of the following recurrences:
    1. 2 T(n / 2) + n
    2. 2 T(n / 2) + √n
    3. 3 T(n / 2) + n
    4. 4 T(n / 2) + n²
    5. 4 T(n / 2) + n
    6. 8 T(n / 2) + n²
    7. 9 T(n / 3) + n³
    8. 2 T(n / 4) + √n
    9. 16 T(n / 4) + n³