CSE 421 Assignment #6
Winter 2005

Due: Friday, February 25, 2005.

Reading Assignment: Kleinberg and Tardos Chapter 7

Problems: For all problems on this homework prove that your algorithm is correct and analyze its worst-case running time.

  1. Kleinberg and Tardos, Section 6.7, Problem 1, page 266.

  2. Modify Karatsuba's algorithm based on splitting the polynomials into 3 pieces instead of two. Base your algorithm on an algorithm for multiplying two degree 2 polynomials that uses evaluation and interpolation. It is possible to do this degree 2 multiplication with as few as 5 multiplications of coefficients. (Note that it is not hard to find a way to do this with 6 multiplications but that algorithm is less efficient than the basic Karatsuba algorithm.) HINT: Use evaluation and interpolation at 5 points.

  3. In class we looked at a simple example of how a dynamic programming algorithm could compute the nth Fibonacci number in O(n) addition steps. (This was a lot better than the natural recursive algorithm which took exponential time!) If we allow multiplication as well as addition we can write some matrix operations that let us compute the nth Fibonacci number F(n) with even fewer operations using divide and conquer: We can write a matrix equation:
    F(k-1)
    F(k)
    =
    01
    11
    .
    F(k-2)
    F(k-1)
    In particular, if we let A be the 2x2 matrix
    01
    11
    then F(n) is the second component of An-1.[0 1]T where [0 1]T is just a column vector with first row 0 and second row 1 and An-1 is n-1 copies of matrix A multiplied together. Use this fact with divide and conquer to design an algorithm that uses only O(log n) multiplications and additions of integers to compute F(n).

  4. Extra credit: The ordinary algorithm for addition of integers is O(n) bit operations where n is the number of bits and the best algorithm for multiplication of integers is O(n log n loglog n) bit operations. Compare the asymptotic costs of the dynamic programming algorithm versus the divide and conquer algorithm from problem 3 above for Fibonacci numbers in terms of total bit operations. Which is better if ordinary O(n2) method for multiplication is used. Which would be better if the fastest multiplication is used? (Remember that the sizes of the numbers themselves are growing as both algorithms procede.)