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.
- Kleinberg and Tardos, Section 6.7, Problem 1, page 266.
- 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.
- 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:
|
|
|
|
|
In particular, if we let A be the 2x2 matrix
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).
- 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.)