(Textbook. Click for information.)

CS 3343/3341  Analysis of Algorithms  Spring 2012  Recitation 8  Exam Review     Week 8: Mar 06-Mar 08 Mid-term Exam: Mar 8, in class  Due (on time): 2012-03-07  21:59:59  No late submission

Recitation 8 should be submitted following directions at: submissions with deadlines 2012-03-07  21:59:59 (that's Wednesday, 7 March 2012, 9:59:59 pm) for full credit. No late submission.

Note (at 1pm, Wednesday): I hadn't been able to ssh or sftp to UTSA since yesterday evening. Finally, the submission program is online and I'm ready to give a password to those who submit. Sorry for this delay. (In using the password, the "User name" or "Account name" should be "CS3343", without the quotes and with caps for "CS". The password is all lowercase.)

Notice: you may bring to class ONE SHEET of paper with anything you like written on it. Just a single sheet, standard size, for yourself alone.

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

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.

   2. In one of the weird topics, we found a special application for the fast exponentiation. What was it?

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

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.

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

7. What does this function do, and what did we use it for in the course?

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

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

• 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³