CSE 421 Assignment #4
Autumn 2007

Due: Friday, October 26, 2007.

Reading Assignment: Kleinberg and Tardos Chapter 5

Problems: Re-read the Grading Guidelines before answering

  1. Kleinberg and Tardos, Chapter 5, Problem 1, page 246

  2. Kleinberg and Tardos, Chapter 5, Problem 5, page 248

  3. Solve each of the following recurrences to get the best asymptotic bounds on T(n) in each case using O( ) notation. You can assume that everything is rounded down to the nearest integer

    1. T(n)= T(n/(2log n))+ 10n for n > 1 and T(1)=1.

    2. T(n)= n1/2 T(n1/2) +5n1/2 for n > 1 and T(1)=1.

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

  5. Extra Credit Show how to solve the second problem above using O(n) time, not using divide and conquer.