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
- Kleinberg and Tardos, Chapter 5, Problem 1, page 246
- Kleinberg and Tardos, Chapter 5, Problem 5, page 248
- 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
- T(n)= T(n/(2log n))+ 10n for n > 1 and T(1)=1.
- T(n)= n1/2 T(n1/2) +5n1/2 for n > 1 and T(1)=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 at 5 points.
- Extra Credit Show how to solve the second problem above using
O(n) time, not using divide and conquer.