CSE 421 Assignment #5
Winter 2003

Due: Friday, Feb 21, 2003.

Reading Assignment: Read Chapter 5 of Kleinberg and Tardos.

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

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

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

  3. Kleinberg and Tardos, Section 5.9, Problem 2, pages 162-3. (Note that there is no figure!)

  4. Extra credit: Kleinberg and Tardos, Section 5.9, Problem 7, page 167-8.

  5. Extra credit: The best 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 2 above for Fibonacci numbers in terms of total bit operations. Which is better? (Remember that the sizes of the numbers themselves are growing as both algorithms procede.)

  6. Extra credit: Feedback on Chapter 5 of Kleinberg and Tardos. This should be sent in e-mail to the address cse421-textbook@cs. Your message should contain your name prominently displayed at the start as well as the number of the chapter for which you are providing comments. If you have more than one comment, your comments should be laid out in some form of numbered or bulleted list.