Avalg homework C, fall 2009
This homework is due 18/11.
It should be done individually and handed in at 10.15 at the beginning of class.
Solutions handed in late are not accepted and will not be graded.
The solutions must be printed, not handwritten.
Multiply the polynomials
x3 + 2x2 + 3x - 1 and
2x3 - x2 - x + 2 using
You only need to show the topmost recursion step of the algorithms.
- a) Karatsuba's algorithm, (5p)
- b) FFT. (5p)
Compute the discrete Fourier transform of the vector
[1,3,5,7] using arithmetic modulo 17. Use the fact
that 5 is a generator of Z17*. (5p)
Evalutating p(x) at a given point x0 can be done
by computing q(x) and r such that
p(x) = q(x)(x - x0) + r.
Clearly, p(x0) = r. Show how to compute r
and the coefficients of q in linear time
from x0 and the coefficients of p. (5p)
Let A = (aij) be a matrix such that
aij = ai-1,j-1 for
i = 2, 3,...,n and
j = 2, 3,...,n. Give an O(n log n)-time
algorithm for multiplying A by a vector of length n. (5p)