Homework 7

1. Poly Multiplication: Problem 2.9 from [DPV] (Practice with polynomial multiplication)
2. Interpolation: A polynomial C of degree ≤ 3 evaluates at the 4-th roots of unity as:
                           C(1) = 5,   C(-1) = 3,  C(i) = i,  C(-i) = -i.
   Determine the coefficients of the polynomial using FFT.
   (You need to show your work.)
3. Cartesian Sum: Consider two sets A and B, each having n integers in the range from 0 to 10n.
   We wish to compute the Cartesian sum of A and B, defined by:
         C = { x + y : x∈ A and y∈ B}.
   Note that integers in C are in the range from 0 to 20n.
   We want to find the set of elements in C and also the number of times each
   element of C is realized as a sum of elements in A and B.
   Show that the problem can be solved in O(nlogn) time by
   reducing it to the polynomial multiplication algorithm.
   Example: A=[1,2,3], B=[2,3]
   then in this case C=[3,4,5,6]
   The output of your algorithm should be something like:
   3 appears and is obtainable in 1 way
   4 appears and is obtainable in 2 ways
   5 appears and is obtainable in 2 ways
   6 appears and is obtainable in 1 way