Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD2440 / avalg09 / Homework / Homework C

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

1. Multiply the polynomials x3 + 2x2 + 3x - 1 and 2x3 - x2 - x + 2 using
• a) Karatsuba's algorithm, (5p)
• b) FFT. (5p)
You only need to show the topmost recursion step of the algorithms.
2. 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)
3. 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)
4. 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)