CSE 417 Assignment #4
Winter 2002

Due: Friday, February 8, 2002.

Midterm: Monday, February 11

Reading:

Problems:

1. Simulate the execution of Karatsuba's polynomial multiplication method on the two polynomials

   P = 1 x ³ + 1 x ² + 1 x + 1
   Q = 2 x ³ - 3 x ² - 4 x + 5

   Show the call tree, i.e. the tree representing the various recursive calls the algorithm would make on this input, including the inputs to and results returned from each call. What is the total number of elementary integer multiplication operations performed by it on this input? What is the total number of elementary integer addition/subtraction operations? (Count only arithmetic operations involving coefficients of the polynomials, not those used for program control, such as calculating array indices or loop control. By "elementary" I mean basic operations supplied by the computer, as opposed to calls to subroutines that you might write. E.g., Karatsuba's algorithm performs elementary multiplications only in the base case, and addition/subtraction only in the non-base case.) Compare these operation counts to the counts for the straightforward O(n²) polynomial multiplication method. Which is better? Do you think your answer would change if the polynomials had been of degree, say, 31 instead of 3?

2. Strassen's matrix multiplication method gives rise to the following recurrence for calculating the total number of elementary arithmetic operations:

   M(1) = c, and
   M(n) = 7 M(n/2) + c n²     for n > 1.

   Show that the solution to this recurrence is O(n^log₂7), (log₂7 = 2.81...). Assume that n is a power of 2. Use the "tree" method shown in lecture and on the slides.

   The following identities that you've probably seen before might be useful:

   1 + x + x² + x³ + ... + x^k = (x^k+1 - 1)/(x - 1) for any x != 1, and
   
   a^log_bn = (b^log_ba)^log_bn = (b^log_bn)^log_ba = n^log_ba,

3. Give a fast divide and conquer algorithm for the following silhouette problem:

   Input: an unordered list of triples (x_l, x_r, h), where 0 < x_l < x_r and 0 < h.

   Problem: Each triple describes a rectangle of height h whose base is on the x axis, and whose left and right sides are at positions x_l and x_r, respectively. Imagine that each rectangle is opaque, and that the whole collection is illuminated from behind. The problem is to calculate the silhouette of the set of rectangles - a description of the visible edges in the resulting scene. (This is a very simple case of what's called hidden line elimination in computer craphics.)

   Output: A list of pairs (x_i,y_i), ordered by increasing x_i, of the coordinates of points where the height of the silhouette changes.

   Example: (Revised 2/4/02.) Given input:

   (1,2,1) (10,12,2) (2,4,1) (5,8,3) (3,6,4)

   the output should be:

   (0,0) (1,0) (1,1) (3,1) (3,4) (6,4) (6,3) (8,3) (8,0) (10,0) (10,2) (12,2) (12,0) (infinity,0).

            INPUT                                           OUTPUT
                                                .
            +--------+                          .           +--------+                   
            |        |                          .           |        |                   
            |        |                          .           |        |                   
            |     +--+-----+                    .           |        +-----+                
            |     |  |     |                    .           |              |
            |     |  |     |                    .           |              |                
            |     |  |     |     +----+         .           |              |     +----+      
            |     |  |     |     |    |         .           |              |     |    |      
            |     |  |     |     |    |         .           |              |     |    |      
      +--+--+--+  |  |     |     |    |         .     +-----+              |     |    |      
      |  |  |  |  |  |     |     |    |         .     |                    |     |    |      
      |  |  |  |  |  |     |     |    |         .     |                    |     |    |      
   +--+--+--+--+--+--+-----+-----+----+------   .  +--+                    +-----+    +------
   0  1  2  3  4  5  6  7  8  9 10   12            0  1  2  3  4  5  6  7  8  9 10   12   
   

   Give a brief English description of your algorithm, plus pseudocode for it. Give a recurrence relation for its running time and solve it. (If the recurrence is one we solved in class, just state that and give the solution; otherwise, justify your solution.)

   Partial credit for correct but non-divide-and-conquer solutions.

4. (Extra Credit) The following recurrence generalizes all of the recurrences for divide and conquer algorithms we've see so far, and many others.

   T(1) = c, and
   T(n) = a T(n/b) + c n^k     for n > 1.

   Show, for any positive integers a, c, k, and any integer b ≥ 2, that its solution is:
   1. if a > b^k then T(n) = Θ(n^log_ba)
   2. if a < b^k then T(n) = Θ(n^k)
   3. if a = b^k then T(n) = Θ(n^klog n)
   You may assume that n is a power of b.

   Loosely speaking, it says that if the number of subproblems is large in comparison to the other parameters, then the work at the leaf level of the recursion tree dominates the run time (case a); if the number of subproblems is small, then the work at the root level dominates (case b), and at the critical in-between value, all levels contribute equally (case c).