Introduction to the Design and Analysis of Algorithms
(Textbook. Click for information.)
 CS 3343/3341
 Analysis of Algorithms
 Spring 2012
 Recitation 6
 Recurrences, etc.
    Complete Answers  

Material About Recurrence Equations. Here are links to material about them, some old and some new:

Recurrence Equations.
  1. Use the Master Theorem to analyze the following recurrences. (The theorem may not work for some of them.)

    [Application of the Master Method to the recurrences is carried out in the table below. Note that the case "Master fails" means that the Master Method does not apply in that case, as explained in the bottom of page 95 and on to 96. Exercise 4.6-2 (page 106) gives a solution in this case, but the material is too technical to come up often.]

    Recurrences, solution by Master Method, Examples
    Recurrenceab logb(a)nlogb(a) f(n)CaseBehavior
    T(n) = 3 T(n / 2) + n2 3 2log2(3) = 1.585 n1.585n2 3 Θ(n2)
    T(n) = 2 T(n / 2) + n2 2 2log2(2) = 1 n1n2 3 Θ(n2)
    T(n) = 64 T(n / 4) + √n 64 4log4(64) = 3 n3n0.5 1 Θ(n3)
    T(n) = 9 T(n / 3) + n2 log(n) 9 3log3(9) = 2 n2n2 log(n) noneMaster fails
    T(n) = 32 T(n / 2) + n2 log(n) 32 2log2(32) = 5 n5n2 log(n) 1 Θ(n5)
    T(n) = 125 T(n / 5) + 1 1255log5(125) = 3 n3n0 = 1 1 Θ(n3)
    T(n) = 16 T(n / 4) + n4 16 4log4(16) = 2 n2n4 3 Θ(n4)
    T(n) = 2 T(n / 4) + √n 2 4log4(2) = 1/2 n1/2 = √n √n 2 Θ(√n log(n))
    T(n) = 2 T(n / 4) + √n log(n) 2 4log4(2) = 1/2 n1/2 = √n √n log(n) noneMaster fails

Priority Queues: See heaps (at the end of this page are links to illustrations of various heap operations, using the same data as in your book), and heapsort (in Java). [Text, pages 151-162.] Following your text, we ignore the 0th element of arrays in Java when working with heaps.

  1. Text, Exercise 6.5-1 on page 164. [Illustrate the operation of Heap-Extract-Max on the heap A = {15,13,9,5,12,8,7,4,0,6,2,1}.]
    [Here are the successive steps:]

    main: heapsize:12, heap: 15 13 9 5 12 8 7 4 0 6 2 1 
maxHeapify: heapsize:11, heap: 1 13 9 5 12 8 7 4 0 6 2 
maxHeapify: heapsize:11, heap: 13 1 9 5 12 8 7 4 0 6 2 
maxHeapify: heapsize:11, heap: 13 12 9 5 1 8 7 4 0 6 2 
maxHeapify: heapsize:11, heap: 13 12 9 5 6 8 7 4 0 1 2 
Max of heap: 15
main: heapsize:11, heap: 13 12 9 5 6 8 7 4 0 1 2

  2. Text, Exercise 6.5-2 on page 165. [Illustrate the operation of Max-Heap-Insert(A, 10) on the heap A = {15,13,9,5,12,8,7,4,0,6,2,1}.]
    [Here are the successive steps:]

    main: heapsize:12, heap: 15 13 9 5 12 8 7 4 0 6 2 1 
maxHeapInsert: heapsize:12, heap: 15 13 9 5 12 8 7 4 0 6 2 1 
heapIncreaseKey: heapsize:13, heap: 15 13 9 5 12 8 7 4 0 6 2 1 -2000000000 
heapIncreaseKey: heapsize:13, heap: 15 13 9 5 12 8 7 4 0 6 2 1 10 
heapIncreaseKey: heapsize:13, heap: 15 13 9 5 12 10 7 4 0 6 2 1 8 
heapIncreaseKey: heapsize:13, heap: 15 13 10 5 12 9 7 4 0 6 2 1 8 
main: heapsize:13, heap: 15 13 10 5 12 9 7 4 0 6 2 1 8

    [Here is the program used for the two questions above (although it was assumed but not required that you would do these questions by hand):]

    // PQueueInt.java: priority queue of integers
public class PQueueInt {

   private int[] A;
   private int heapsize;

   public PQueueInt(int[] Ap, int hs) {
      A = Ap;
      heapsize = hs;
   }

   public int qSize() { return heapsize; }

   public int heapMaximum() {
      if (heapsize < 1) {
         System.out.println("Empty Queue");
         System.exit(0);
      }
      return A[1];
   }

   public int heapExtractMax() {
      if (heapsize < 1) {
         System.out.println("Heap Underflow");
         System.exit(0);
      }
      int max = A[1];
      A[1] = A[heapsize];
      heapsize--;
      maxHeapify(1);
      return max;
   }

   private int parent(int i) {return i/2;}
   private int left  (int i) {return 2*i;}
   private int right (int i) {return 2*i + 1;}

   private void exchange(int i, int largest) {
      int temp = A[i];
      A[i] = A[largest];
      A[largest] = temp;
   }

   private void maxHeapify(int i) {
      printheap("maxHeapify");
      int l = left(i);
      int r = right(i);
      int largest;
      if (l <= heapsize && A[l] > A[i])
         largest = l;
      else largest = i;
      if (r <= heapsize && A[r] > A[largest])
         largest = r;
      if (largest != i) {
         exchange(i, largest); 
         maxHeapify(largest);
      }
   }

       public void maxHeapInsert(int key) {
      if (heapsize >= A.length - 1) {
         System.out.println("Heap Overflow");
         System.exit(1);
      }
      printheap("maxHeapInsert");
      heapsize++;
      A[heapsize] = -2000000000;
      heapIncreaseKey(heapsize, key);
   }

   void heapIncreaseKey(int i, int key) {
      if (key < A[i]) {
         System.out.println("New key < Current");
         System.exit(2);
      }
      printheap("heapIncreaseKey");
      A[i] = key;
      printheap("heapIncreaseKey");
      while (i > 1 && A[parent(i)] < A[i]) {
         exchange(i, parent(i));
         i = parent(i);
         printheap("heapIncreaseKey");
      }
   }

   public void printheap(String id) {
      System.out.print(id + ": heapsize:" +
         heapsize + ", heap: ");
      for (int i = 1; i <= heapsize; i++) {
         System.out.print(A[i] + " ");
      }
      System.out.println();
   }

   public static void main(String[] args) {
      int[] A =
         {0,15,13,9,5,12,8,7,4,0,6,2,1,-1,-1,-1};
      int heapsize = 12;
      PQueueInt pq = new PQueueInt(A, heapsize);
      pq.printheap("main");

      // do one of the other of the two below:
         System.out.println("Max of heap: " +
            pq.heapExtractMax()); // Problem 2

         // pq.maxHeapInsert(10); // Problem 3

      pq.printheap("main");
   }
}

  3. Text, Exercise 6.5-4 on page 165. [Why do we bother setting the key of the inserted node to -∞ in line 2 of Max-Heap-Insert when the next thing we do is increase its key to the desired value?] [When I assigned this problem I thought there was a simple answer. In the use on page 163, the location of A[A.heapsize] could be given any value at all or left undefined and the Heap-Increase-Key would still work as long as the check and error message was left off. The Heap-Increase-Key algorithm works for any node i, but for non-leaf nodes the check and error message is required. If you want to keep the Heap-Increase-Key as it is in its general form, then you need to set A[A.heapsize] = -∞ to guarantee that the result is a heap and that the general algorithm will work. Kind of a lame reason.]

Induction:
  1. Use mathematical induction to prove the following. (It will not suffice to show that the formula is true for some specific values of n, such as n = 5, but you must prove it in general. Don't forget the basis. This is easier than you might expect.)

    [First the basis: for n = 0, the equation says that F0 = F2 - 1, and this is true. Assume the equation is true for an arbitrary k >= 0, that is, assume that

    Then to prove: the same identity for k+1:

    But the left hand side above is

Strassen''s Algorithm for Matrix Multiplication:
  1. Text, Exercise 4.2-7 on page 83. [Show how to multiply the complex numbers a + bi and c + di using only three multiplications of real numbers. The algorithm should take a, b, c, and d as input and produce the real component ac - bd and the imaginary component ad + bc separately. Hint: This is the same as the trick in the method for multiplying integers faster ( Multiply in Θ(n1.585) ). Consider the expression (a + b)*(c + d).] [Using three multiplications, calculate:

      m1 = (a + b)*(c + d)
      m2 = a*c
      m3 = b*d

    Then

      m1 - m2 - m3 = a*d + b*c, and
      m2 - m3 = a*c - b*d

  2. Suppose we want to mimic Strassen's approach using 3-by-3 matrices. Use a divide and conquer strategy for this case, where one will divide a 9-by-9 matrix into nine 3-by-3 matrices, and so on for larger powers of 3. First examine the standard way to multiply two 3-by-3 matrices, and see that this takes 27 multiplications. Write a recurrence for this situation. Use the Master Theorem to show that T(n) = Θ(n3) for your new recurrence.
    [Hints: The new recurrence is similar to the one for ordinary 2-by-2 matrices, which was T(n) = 8 T(n / 2) + Θ(n2), as explained in your text, page 78.] [The recurrence is T(n) = 27 T(n / 3) + Θ(n2), and here a = 27, b = 3, f(n) is Θ(n2), so we compare and see that

      n2 = f(n) < nlog3(27) = n3

    so case 1 applies and this is an Θ(n3) algorithm.]

  3. Continuing the previous problem, one might look for a clever way to multiply 3-by-3 matrices, using fewer than 27 individual multiplications. We might work very hard and find a way to do this in, say, 23 multiplications, only to find that the work was useless, because the asymptotic bound in this case was worse that Strassen's bound for the 2-by-2 case. What is the biggest integer k that has the property that if we can multiply 3-by-3s in k multiplications, we would have a better bound than Strassen? [In other words, how far would we have to push the number down? What's the biggest k that would still improve on Strassen?] You should solve this problem by writing a recurrence for 3-by-3 matrices involving the variable k. Use the Master Theorem to solve this recurrence. [Suppose we can multiply 3-by-3 matrices in k scalar multiplications. Then the recurrence is

      T(n) = k T(n / 3) + Θ(n2),

    From the Master Method we want to consider the value log3(k). As long as this is < 3, we know that the algorithm will be Θ(nlog3(k)). In order to be better than Strassen, we want

      log3(k) < log2(7) = 2.807355 (Strassen's exponent)

    Taking 3 to the value on each side, we get

      3log3(k) < 3log2(7) = 32.807355, or
      k < 21.84986

    Thus k = 21 is the largest value that would still give an improvement on Strassen's result. (Of course, it is not possible to get such a result.)

    The performance for the value k = 21 would be Θ(nlog3(21)) = Θ(n2.77124375).]

Revision date: 2012-03-02. (Please use ISO 8601, the International Standard.)