Avalg homework C fall 2007

This homework is due 3/12. It should be done individually and handed in at the beginning of the homework session. You should be prepared to present your homework orally in class. This is part of the examination and you have to attend the homework session to get credit for your homework. Solutions handed in late are not accepted and will not be graded.

1. Multiply the polynomials x3 + 2x2 + 3x + 4 and 3x3 + 2x2 - x + 1 using

  • a) Karatsuba's algorithm, (5p)
  • b) FFT. (5p)

2. Compute the discrete Fourier transform of the vector [1,1,2,2] 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)


Stefan Nilsson
2007-11-13