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.
- 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.
- 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).
- Kleinberg and Tardos, Section 5.9, Problem 2, pages 162-3.
(Note that there is no figure!)
- Extra credit: Kleinberg and Tardos, Section 5.9, Problem 7, page 167-8.
- 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.)
- 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.