CSE 417, Wi '05: Assignment #4, Due: Wednesday, February 16, 2005

CSE Home

About Us

Search

Contact Info

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

   1. 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.
   2. 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 scalar (non-vector) 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.)
   3. 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?
   4. Give a precise recurrence relation for the number of elementary multiplications required by Karatsuba's method to multiply two degree n-1 ≥ 0 polynomials, for n a power of two. Repeat this for the number of additions/subtractions. Calculate the exact solutions to these recurrences for n=32 and compare them to your estimates in step c. (You do not need to find the asymptotic solutions to these recurrences, which should both be O(n^1.59...) as shown in lecture.)

2. Modify Karatsuba's algorithm based on splitting the polynomials into three pieces instead of two. Base your algorithm on an algorithm for multiplying two degree 2 polynomials. The "obvious" way to do this would use nine multiplications -- multiply all nine coefficient pairs (one from each of the two degree two polynomials). Any method using fewer than nine multiplications should result in an algorithm that is asymptotically faster that the "obvious" quadratic time method.
   1. Find such a method. (Partial credit for 7-8 multiplies; full credit for 6 multiplies; extra credit for 5 multiplies. Especially for the extra credit version, it may help to think about Karatsuba's method in a slightly different way. Let P(c), Q(c) denote the polynomials P(x) and Q(x) evaluated at the point x=c. Two of Karatsuba's three multiplies are P(0)*Q(0) and P(1)*Q(1). Are there other points at which evaluation of the two polynomials would be convenient/useful?)
   2. What's the asymptotic running time of your algorithm?
   3. Is this better or worse than Karatsuba's algorithm?

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

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

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

5. (Extra Credit) The following recurrence generalizes all of the recurrences for divide and conquer algorithms we've seen 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, and c, any k ≥ 0, 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).

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to cse417-webmaster@cs.washington.edu]