Algorithms Tutorial Problems 2
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.
2. You and a friend find yourselves on a TV game show! The game works as
follows. There is a hidden N×N table A. Each cell A[i, j] of the table contains
a single integer and no two cells contain the same value. At any point in time,
you may ask the value of a single cell to be revealed. To win the big prize,
you need to find the N cells each containing the maximum value in its row.
Formally, you need to produce an array M [1..N ] so that A[r,M [r]] contains the
maximum value in row r of A, i.e., such that A[r,M [r]] is the largest integer
among A[r, 1], A[r, 2], . . . , A[r,N ]. In addition, to win, you should ask at most
O(N log N) many questions. For example, if the hidden grid looks like this:
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
1
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(N log N) many questions that pro-
duces 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(
Fn+1 Fn
Fn Fn−1
)
=
(
1 1
1 0
)n
for all integers n ≥ 1.
(b) Hence or otherwise, give an algorithm that finds Fn in O(log n) time.
Hint: You may wish to refer to Example 1.5 on page 28 of the “Review Ma-
terial” found as lecture notes for Topic 0 on the Course Resources page of the
course website.
4. Design an algorithm which multiplies a polynomial of degree 16 with a polyno-
mial 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 num-
ber of multiplications of large numbers (large numbers are those which depend
on the coefficients and thus can be arbitrarily large).
(a) P (x) = a0 + a2x
2 + a4x
4 + a6x
6; Q(x) = b0 + b2x
2 + b4x
4 + b6x
6 using at
most 7 multiplications of large numbers;
(b) P (x) = a0 + a100x
100 and Q(x) = b0 + b100x
100 with at most 3 multiplica-
tions of large numbers.
2
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 multipli-
cations.
7. Describe all k which satisfy ı̇ ω1364ω
11
32 = ω
k
64 (ı̇ is the imaginary unit).
8. What are the real and the imaginary parts of eı̇
π
4 ? 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) =
∑
i+j=m
0≤i,j≤n
i3j2
(b)
F (m) =
∑
i+j=m
0≤i,j≤n
log(j + 1)i
in time O(n log n).
10. (a) Compute by any method you wish the (linear) convolution s ∗ s of the
sequence s = 〈1, 2, 0, 4〉 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) se-
quences?
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
3
(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 help-
ful 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!
12. You have a set of N coins in a bag, each having a value between 1 and M ,
where M ≥ N . Some coins may have the same value. You pick two coins
(without replacement) and record the sum of their values. Determine what
possible sums can be achieved, in O(M logM) time.
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
P (x) = (x− ω064)(x− ω
1
64)(x− ω
2
64) . . . (x− ω
63
64)
(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 recur-
sively FFT and obtain FFT (a0, a2, a4, a6) and FFT (a1, a3, a5, a7). Proceed-
ing 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 re-
cursion tree of the original input sequence. Given any input (a0, a1, a2, . . . , a2n−1)
describe the permutation of the leaves of the recursion tree.
4
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 = 〈a0, a1, . . . , an−1〉
of length n and sequence
B = 〈1, 0, 0, . . . , 0︸ ︷︷ ︸
k
,−1〉
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 + a2x
2 + a3x
3 and a
polynomial Q(x) = b0 + b1x + b2x
2 + b3x
3 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
〈a0, a1, . . . , an−1〉
is the sequence of values
〈P (ω0n), P (ω
1
n), P (ω
2
n), . . . , P (ω
n−1
n )〉
of the associated polynomial P (x) = a0+a1x+a2x
2+ . . .+an−1x
n−1. Compute
directly (i.e., without using the FFT) and maximally simplify the DFT of the
following sequences:
5
(a) 〈1, 0, . . . , 0︸ ︷︷ ︸
n−1
〉
(b) 〈 0, . . . , 0,︸ ︷︷ ︸
n−1
1〉
(c) 〈 1, . . . , 1︸ ︷︷ ︸
n
〉
6