Description

Divide-and-Conquer, FFT and Convolution
1. You are given a 2n × 2n board with one of its cells missing (i.e., the board has a hole); the position of the missing cell can be arbitrary. You are also given a supply of “dominoes” each containing 3 such squares; see the figure: Your task is to design an algorithm which covers the entire board with such

“dominoes” except for the hole.
Column 1 Column 2 Column 3 Column 4
Row 1 10 5 8 3
Row 2 1 9 7 6
Row 3 -3 4 -1 0
Row 4 -10 -9 -8 2
then the correct output would be M = [1,2,2,4].
Your friend has just had a go, and sadly failed to win the prize because they asked N2 many questions which is too many. However, they whisper to you a hint: they found out that M is non-decreasing. Formally, they tell you that M[1] ≤ M[2] ≤ ··· ≤ M[N] (this is the case in the example above). Design an algorithm which asks at most O(NlogN) many questions that produces the array M correctly, even in the very worst case.
Hint: Note that you do not have enough time to find out the value of every cell in the grid! Try determining M[N/2] first, and see if divide-and-conquer is of any assistance.
3. Let us define the Fibonacci numbers as F0 = 0, F1 = 1 and Fn = Fn−1 + Fn−2 for all n ≥ 2. Thus, the Fibonacci sequence looks as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
(a) Show, by induction or otherwise, that

for all integers n ≥ 1.
(b) Hence or otherwise, give an algorithm that finds Fn in O(logn) time.
4. Design an algorithm which multiplies a polynomial of degree 16 with a polynomial of degree 8 using only 25 multiplications in which both operands (which both depend on the coefficients of the polynomial) can be arbitrarily large.
5. Multiply the following pairs of polynomials using at most the prescribed number of multiplications of large numbers (large numbers are those which depend on the coefficients and thus can be arbitrarily large).
(a) P(x) = a0 + a2x2 + a4x4 + a6x6; Q(x) = b0 + b2x2 + b4x4 + b6x6 using at most 7 multiplications of large numbers;
(b) P(x) = a0 + a100x100 and Q(x) = b0 + b100x100 with at most 3 multiplications of large numbers.
6. (a) Multiply two complex numbers (a + ıb˙ ) and (c + ıd˙ ) (where a,b,c,d are all real numbers) using only 3 real number multiplications.
(a) Find (a + ıb˙ )2 using only two multiplications of real numbers.
(b) Find the product (a + ıb˙ )2(c + ıd˙ )2 using only five real number multiplications.
7. Describe all k which satisfy ˙ is the imaginary unit).
8. What are the real and the imaginary parts of e ? Compute the DFT of the sequence A = (0,1,2,3,4,5,6,7) by applying the FFT algorithm by hand.
9. Describe how you would compute all elements of the sequence F(0),F(1),F(2),…,F(2n) where
(a)
F(m) = X i3j2
i+j=m
0≤i,j≤n
(b)
F(m) = X log(j + 1)i
i+j=m 0≤i,j≤n
in time O(nlogn).
10. (a) Compute by any method you wish the (linear) convolution s ∗ s of the sequence s = h1,2,0,4i with itself. (Note that there is no requirement on the efficiency of your method, and that the sequence is really short!)
(b) If a sequence x has n terms and sequence y has k terms, how many terms does the convolution x ∗ y of these two sequences have?
(c) Is it true that s ∗ t = t ∗ s for any two sequences s and t? Explain why or why not.
(d) Describe how we compute efficiently the convolution of two (long) sequences?
11. In this part we will extend the convolution algorithm described in class to multiply multiple polynomials together (not just two).
Suppose you have K polynomials P1,…,PK each of degree at least one, and that
degree(P1) + ··· + degree(PK) = S
(i) Show that you can find the product of these K polynomials in O(KS logS) time.
Hint: consider using divide-and-conquer; a tree structure might be helpful here as well. Also, remember that if x,y,z are all positive, then log(x + y) < log(x + y + z)
(ii) Show that you can find the product of these K polynomials in O(S logS logK) time. Explain why your algorithm has the required time complexity. Hint: consider using divide-and-conquer!
For example, if there are N = 3 coins in the bag with values 1, 4 and 5 (so we could have M = 5), then the possible sums are 5, 6 and 9.
Hint: if the coins have values v1,…,vN, how might you use the polynomial xv1 + ··· + xvN?
13. Consider the polynomial

(a) Compute P(0);
(b) What is the degree of P(x)? What is its coefficient of the highest degree of x present in P(x)?
(c) What are the values of P(x) at the roots of unity of order 64?
(d) Can you represent P(x) in the coefficient form without any computation?
Hint: two polynomials of the same degree which have the same coefficient in front of the largest power and have the same zeros are equal.
14. To apply the FFT to the sequence (a0,a1,a2,a3,a4,a5,a6,a7) we apply recursively FFT and obtain FFT(a0,a2,a4,a6) and FFT(a1,a3,a5,a7). Proceeding further with recursion, we obtain FFT(a0,a4) and FFT(a2,a6) as well as FFT(a1,a5) and FFT(a3,a7). Thus, from bottom up, (a0,a1,a2,a3,a4,a5,a6,a7) is obtained using permutation (a0,a4,a2,a6,a1,a5,a3,a7) as the leaves of the recursion tree of the original input sequence. Given any input (a0,a1,a2,…,a2n−1) describe the permutation of the leaves of the recursion tree.
Hint: write indices in binary and see what the relationship is of the bits of the ith element of the original sequence and the ith element of the resulting permutation of elements as they appear on the leaves on the recursion tree. From there use induction to prove the general statement 15. You are given a sequence
A = ha0,a1,…,an−1i
of length n and sequence

of length k + 2, where 1 ≤ k ≤ n/4.
(a) Compute the DFT of sequence B.
(b) Compute the convolution sequence C = A∗B in terms of the elements of sequence A.
(c) Show that in this particular case such a convolution can be computed in time O(n).
16. (a) Compute the DFT of the sequence (1,−1,−1,1) by any method you wish.
(b) Compute the linear convolution of sequences (1,−1,−1,1) and (−1,1,1,−1) by any method you wish.
17. Assume that you are given a polynomial P(x) = a0 + a1x + a2x2 + a3x3 and a polynomial Q(x) = b0 + b1x + b2x2 + b3x3 whose coefficients can be arbitrarily large numbers. Let R(x) = P(x)2 − Q(x)2. Compute the coefficients of R(x) using only 7 large number multiplications. 18. Recall that the DFT of a sequence
ha0,a1,…,an−1i
is the sequence of values

of the associated polynomial P(x) = a0 +a1x+a2x2 +…+an−1xn−1. Compute directly (i.e., without using the FFT) and maximally simplify the DFT of the following sequences: