Algorithms Tutorial 2 Solutions
Divide and Conquer, polynomial multiplication and FFT
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.
Solution: We proceed by a divide and conquer recursion; thus, we split the board into 4 equal parts:
We can now apply our recursive procedure to the top left board which has a missing square. To be able to apply recursion to the remaining 3 squares we place a domino at the centre as shown below.
We treat the covered squares in each of the three pieces as a missing square and can proceed by recursion applied on all 4 squares whose sides are half the size of the size of the original square.
1
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:
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
2
Column 1
Column 2
Column 3
Column 4
Row 1 Row 2 Row 3 Row 4
10
1 -3 -10
5
9 4 -9
8
7 -1 -8
3 6 0 2
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.
Solution: We first find M[N/2]. We can do this in N questions by simply examining each element in row N/2, and finding the largest one. Suppose M[N/2]=x. Then,weknowforalli
Note that at each stage of recursion in every column at most two cells are investigated; in the first call of recursion only one cell has been investigated in each column (blue cells, max found in the dark blue cell); in the second call of recursion two cells were investigated in only one column (green cells), in the third call of recursion two cells were investigated only in three columns etc. So in each recursion call at most 2N cells were investigate and there are at most log2(N) many recursion calls thus resulting in inspection of at most 2N log2 N many cells as required.
3. Let us define the Fibonacci numbers as F0 = 0, F1 = 1 and Fn = Fn−1 +Fn−2 3
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 1 1n
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.
Solution
(a) Whenn=1wehave
FF=10 n n−1
Fn+1 Fn 1 1 FF=10
1 11 =10
n n−1
so our claim is true for n = 1.
Let k ≥ 1 be an integer, and suppose our claim holds for n = k (Inductive
Hypothesis). Then
1 1k+1 1 1k 1 1
10 =10 10
Fk+1 Fk 1 1 = Fk Fk−1 1 0
by the Inductive Hypothesis. Hence
1 1k+1 Fk+1 +Fk Fk+1
10 =Fk+Fk−1 Fk Fk+2 Fk+1
= Fk+1 Fk
by the definition of the Fibonacci numbers. Hence, our claim is also true
for n = k + 1, so by induction it is true for all integers n ≥ 1. 4
(b) Let
1 1 G=10
and suppose we know Gx. Then, we can compute G2x by simply squaring Gx, which takes O(1) time. Since it is enough to compute Gn, we can do so by first computing G2t for all t ≤ ⌊log2 n⌋: we can do this in O(log n) steps by repeatedly squaring G.
Then, we can consider the base 2 representation of n: this tells us precisely which G2t matrices we should multiply together to obtain Gn.
As an alternative (and equivalent) solution, we can proceed by divide and conquer. To compute Gn: if n is even, recursively compute Gn/2 and square it in O(1). If n is odd, recursively compute G(n−1)/2, square it and then multiply by another G: this last step also occurs in O(1). Since there are O(log n) steps of the recursion only, this algorithm runs in O(log n).
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.
Solution: The product of a polynomial A(x) of degree 16 and a polynomial B(x) of degree 8 is a polynomial C(x) of degree 24; thus, to uniquely determine C(x) we need its values at 25 inputs, so we choose
x = −12,−11,…,−1,0,1,…,12.
We now evaluate A(i) and B(i) for all i such that −12 ≤ i ≤ 12. Note that this does not involve any multiplication of two arbitrarily large numbers but only multiplications of one arbitrarily large number (a coefficient of A(x) or B(x)) with a constant. Notice that the constant involved can be very large, such as 1216 occurring when we evaluate A(12) = A0 + A1 × 12 + … + A16 × 1216). We now perform 25 large number multiplications which produce the values of the product polynomial C(x) = A(x)B(x) at inputs ranging from −12 to 12. Having found C(−12) = A(−12)B(−12),…,C(12) = A(12)B(12), we now solve the following system of 25 linear equations in variables C0, . . . , C24:
{C0 +C1i+C2i2 +…+C24i24 =C(i)=A(i)B(i) : −12≤i≤12} Solving such a system expresses the solutions for C0, . . . , C24 as a linear com-
bination of values of C(i) and thus involves only constants times large values 5
multiplications. So in total we have used only 25 multiplications where both numbers can be arbitrarily large, because they depend on the values of the coefficients of polynomials A(x) and B(x).
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 +a2x2 +a4x4 +a6x6; Q(x) = b0 +b2x2 +b4x4 +b6x6 using at most 7 multiplications of large numbers;
(b) P (x) = a0 + a100 x100 and Q(x) = b0 + b100 x100 with at most 3 multiplica- tions of large numbers.
Solution:
(a) Note that using the substitution y = x2 reduces P(x) to P∗(y) = a0 + a2y+a4y2 +a6y3 and Q(x) to Q∗(y) = b0 +b2y+b4y2 +b6y3. The product R∗(y) = P∗(y)Q∗(y) of these two polynomials is of degree 6 so to uniquely determine R∗(y) we need 7 of its values. Thus, we evalu- ate P∗(y) and Q∗(y) at seven values of its argument x, by letting x = −3, −2, −1, 0, 1, 2, 3. We then obtain from these 7 values of R∗(y) its coefficients, by solving the corresponding system of linear equation in co- efficients r0,…,r6 such that R∗(j) = r0 +r1x+…+r6x6. Thus we solve the system {6j=0 rjij = R∗(i) : −3 ≤ i ≤ 3}. We now form the poly- nomial R∗(j) = r0 + r1x + . . . + r6x6 with thus obtained rj and finally substitute back y with x2 obtaining R(x) = P (x)Q(x).
(b) We use (essentially) the Karatsuba trick:
(a0 + a100x100)(b0 + b100x100) = a0b0 + (a0b100 + b0a100)x100 + a100b100x200
= a0b0 + ((a0 + a100)(b0 + b100) − a0b0 − a100b100)x100 + a100b100x200
Note that the last expression involves only three multiplications: a0b0, a100b100
and (a0 + a100)(b0 + b100). 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. 6
(b) Find the product (a + ı ̇ b)2(c + ı ̇ d)2 using only five real number multipli- cations.
Solution:
(a) This is again the Karatsuba trick:
(a+ı ̇b)(c+ı ̇d) = ac−bd+(bc+ad)ı ̇ = ac−bd+((a+b)(c+d)−ac−bd)ı ̇
so we need only 3 multiplications: ac and bd and (a + b)(c + d).
(a) (a+ı ̇b)2 =a2 −b2 +2abı ̇=(a+b)(a−b)+(a+a)bı ̇.
(b) Just note that (a + ı ̇b)2(c + ı ̇d)2 = ((a + ı ̇b)(c + ı ̇d))2; you can now use (a) to multiply (a + ı ̇ b)(c + ı ̇ d) with only three multiplications and then you can use (b) to square the result with two additional multiplications.
7. Describe all k which satisfy ı ̇ ω13ω11 = ωk (ı ̇ is the imaginary unit). 6432 64
Solution: This problem only tests your understanding of the roots of unity: note that ı ̇ = ω and, by the cancelation lemma, that ω11 = ω22. Thus
4 32 64
ı ̇ ω13ω11 = ω ω13ω22 = ω16ω13ω22 = ω 416+13+22 = ω51 = ω51+64k 64 32 4 64 64 64 64 64 6 64 64
where k is an arbitrary integer (positive or negative). ı ̇ π
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.
Solution: Note that 884
√√√
ω =eı ̇2π =eı ̇π =cosπ+ı ̇sinπ= 2+ı ̇ 2= 2(1+ı ̇). 44222
The polynomial associated with the given sequence is P(x)=x+2×2 +3×3 +4×4 +5×5 +6×6 +7×7
We split it into even and odd powers
P(x)=(2×2 +4×4 +6×6)+x(1+3×2 +5×4 +7×6)
We now let
P[0](y)=2y+4y2 +6y3; P[1](y)=1+3y+5y2 +7y3
7
Then we have
We have to evaluate P(x) at all roots of unity of order 8. Thus we have for
k = 0,1,2,3
P(ω8k) = P[0](ω4k) + ω8kP[1](ω4k) (1) P(ω4+k) = P[0](ωk) − ωkP[1](ωk) (2)
WenowhavetocomputeP[0](ω4k)andP[1](ω4k)fork=0,1,2,3. Wecouldagain split the two polynomial into even and odd powers, but since their degree is low we can compute these values directly, also because the roots of unity of order4aresosimple: ω40 =1,ω41 =ı ̇,ω42 =−1andfinallyω43 =−ı ̇. Wenow have for P[0](y) = 2y + 4y2 + 6y3:
P[0](ω40) = P[0](1) = 2 + 4 + 6 = 12; P[0](ω41)=P[0](ı ̇)=2ı ̇+4ı ̇2 +6ı ̇3 =2ı ̇−4−6ı ̇=−4−4ı ̇; P[0](ω42) = P[0](−1) = −2 + 4 − 6 = −4;
P [0](ω43) = P [0](− ı ̇) = −2 ı ̇ −4 + 6 ı ̇ = −4 + 4 ı ̇;
and similarly for P[1](y) = 1 + 3y + 5y2 + 7y3:
P[1](ω40) = P[1](1) = 1 + 3 + 5 + 7 = 16; P[1](ω41)=P[1](ı ̇)=1+3ı ̇+5ı ̇2 +7ı ̇3 =1+3ı ̇−5−7ı ̇=−4−4ı ̇; P[1](ω42) = P[1](−1) = 1 − 3 + 5 − 7 = −4; P[1](ω43)=P[1](−ı ̇)=1−3ı ̇+5ı ̇2 +7−ı ̇3 =1−3ı ̇−5+7ı ̇=−4+4ı ̇
√√
wealsocompute: ω0 =1;ω1 = 2(1+ı ̇);ω2 =ı ̇;ω3 = 2(−1+ı ̇). 882882
P(x) = P[0](x2) + xP[1](x2)
8484
8
We can now substitute k = 0, 1, 2, 3 in (1) and (2): P(ω80) = P[0](ω40) + ω80P[1](ω40) = 12 + 16 = 28
P(ω4+0) = P[0](ω0) − ω0P[1](ω0) = 12 − 16 = −4 8484√2 √
P(ω81)=P[0](ω41)+ω81P[1](ω41)=−4−4ı ̇+2(1+ı ̇)(−4−4ı ̇)=−4−4(1+ 2)ı ̇ √2 √
P(ω4+1)=P[0](ω1)−ω1P[1](ω1)=−4−4ı ̇− (1+ı ̇)(−4−4ı ̇)=−4−4(1− 2)ı ̇) 84842
P(ω82) = P[0](ω42) + ω82P[1](ω42) = −4(1 + ı ̇)
P (ω4+2) = P [0](ω2) − ω2P [1](ω2) = −4(1 − ı ̇) √
8484
P(ω83)=P[0](ω43)+ω83P[1](ω43)=−4+4ı ̇+ 2(−1+ı ̇)(−4+4ı ̇)=−4+ı ̇(4−4√2)
2
√2 √
P(ω4+3)=P[0](ω3)−ω3P[1](ω3)=−4+4ı ̇− (−1+ı ̇)(−4+4ı ̇)=−4+ı ̇(4+4 2) 84842
√√
Thus, A = ⟨28, −4−4(1+ 2)ı ̇, −4(1+ı ̇), −4+4(1− √√
2)ı ̇, −4, −4−
9. DescribehowyouwouldcomputeallelementsofthesequenceF(0),F(1),F(2),…,F(2n)
4(1− 2)ı ̇, −4(1−ı ̇), −4+(4+4 2)ı ̇⟩ where
(a)
(b)
in time O(n log n).
F(m)= i3j2 i+j =m
0≤i,j ≤n
F(m)= log(j+1)i i+j =m
0≤i,j ≤n
Solution: Note that the first sequence is just the convolution of sequences A = ⟨0,1,23,33,43,…,n3⟩ and B = ⟨0,1,22,32,42,…,n2⟩, while the second sequence can be written as
F(m)= log(j+1)i = ilog(j+1),
i+j =m 0≤i,j ≤n
i+j =m 0≤i,j ≤n
9
10.
so it is a convolution of sequences
C = ⟨0,1,2,3,4,…,n⟩ and D = ⟨log1,log2,log3,log4,log5,…,logn⟩.
Both convolutions can be efficiently evaluated by computing their DFT of their zero paddings to length 2n − 1, using the FFT algorithm, multiplying the corresponding values and then taking the inverse DFT of the product.
(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?
Solution:
(a) For s = ⟨1, 2, 0, 4⟩ the associated polynomial is S(x) = 1 + 2x + 4×3; thus the convolution of s with itself is the sequence of the coefficients of the polynomial S2(x) = (1+2x+4×3)2 = 1+4x+4×2 +8×3 +16×4 +16×6, i.e., the sequence s = ⟨1, 4, 4, 8, 16, 0, 16⟩.
(b) If a sequence has n terms the corresponding polynomial is of degree n−1; thus the product of the two polynomials is of degree n−1+k−1 = n+k−2 and consequently it has n + k − 1 many coefficients.
(c) Since the product of the two corresponding polynomials is commutative, so is the convolution.
(d) A convolution of a sequence of length n and a sequence of length m can be efficiently evaluated by computing their DFT of their zero paddings to length n+m−1, using the FFT algorithm, multiplying the corresponding values and then taking the inverse DFT of the product.
In this part we will extend the convolution algorithm described in class to multiply multiple polynomials together (not just two). SupposeyouhaveKpolynomialsP1,…,PK eachofdegreeatleastone,and that
degree(P1) + · · · + degree(PK ) = S 10
11.
(i) ShowthatyoucanfindtheproductoftheseKpolynomialsinO(KSlogS) 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) ShowthatyoucanfindtheproductoftheseKpolynomialsinO(SlogSlogK) time. Explain why your algorithm has the required time complexity.
Hint: consider using divide-and-conquer!
Solution
(a) Call our two polynomials P and Q. Since both have degree (at most) n, their product PQ will have degree at most 2n. Thus, it suffices to know the value of P Q at 2n + 1 distinct points to uniquely determine it.
We use FFT to evaluate P and Q at values which are the roots of unity of order which is the smallest power of two no less than 2n + 1; this can be done in O(n log n) time. This converts the polynomials from coefficient form to value form. We then multiply the value of P with the value of Q at each point to obtain the value form of PQ (at these points). We then use the Inverse FFT to retrieve PQ in the coefficient form in O(nlogn), as required.
(b) We obtain the products Π(i) = P1(x)·P2(x) . . .·Pi(x) for all 1 ≤ i ≤ K by a simple recursion. Initially, Π(1) = P1(x), and for all i < K we clearly have Πi+1 = Π(i) · Pi+1(x). At each stage, the degree of the partial product Π(i) and of polynomial Pi+1(x) are both less than S, so each multiplication, if performed using fast evaluation of convolution (via the FFT) is bounded by the same constant multiple of S log S. We perform K such multiplications, so our total time complexity is O(KS log S), as required.
Alternatively, pad all polynomials to a degree which is the smallest power of 2 larger than S and find the FFT of all of these polynomials, which will be K sequences of fewer than 2S many values. This requites taking K FFTs each in time Θ(S log S) so in total Θ(KS log S) many operations. Now multiply point-wise all these K sequences, using (K − 1)S multiplications to get a single sequence of length S. Take the Inverse FFT of that sequence in time Θ(S log S). Thus, in total the complexity is Θ(K S log S).
(c) The easiest way is, just as in the Celebrity Problem, to organize polyno- mials and their intermediate products into a complete binary tree, a trick
11
P1P2P3 P4P5P6P7P8P9
P1P2P3 P4P5
P1P2P3 P4P5
P6P7 P8P9 P6P7 P8P9
P7 P8 P9
P1P2
P1 P2
P3 P4
P5 P6
Figure 1: Here K = 9; thus, m = ⌊log2 K⌋ = 3 and we add two children to K−2m = 9−23 = 1 leaf of a perfect binary tree with 8 leaves. Thus obtained tree has 9 leaves.
which is useful in many situations which involve recursively operating on pairs of objects. To remind you of the construction of a complete binary tree, we first compute m = ⌊log2 K⌋ and construct a perfect binary tree with 2m ≤ K leaves (i.e., a tree in which each node except the leaves has precisely two children and all the leaves are at the same depth). If 2m < K add two children to each of the leftmost K − 2m leaves of such a perfect binary tree. In this way you obtain 2(K − 2m) + (2m − (K − 2m)) = 2K−2m+1+2m−K+2m =Kleavesexactly,buteachleafnowhasits pair, and the depth of each leaf is either ⌊log2 n⌋ or ⌊log2 n⌋ + 1, see the picture on the next page. Each leaf is now assigned one of the polynomials and the inner nodes of the tree represent partial products of polynomials corresponding to the two children. Note that, with the possible exception of the deepest level ⌊log2 n⌋ + 1 of the tree (which in the example on the picture contains only two polynomials), the sum of the degrees of polyno- mials on each level is equal to the sum of the degrees of all K polynomials Pi(x), i.e. is equal to S. Let d1 and d2 be the degrees of two polynomials corresponding to the children of a node at some level k; then the prod- uct polynomial is of degree d1 + d2 and thus it can be evaluated (using the FFT to compute the convolution of the sequences of the coefficients) in time O((d1 + d2) log(d1 + d2)) which is also O((d1 + d2) log S), because clearly log(d1 + d2) ≤ log S. Adding up such bounds for all products on level k we get the bound O(S log S), because the degrees of all polynomials at each of the levels add up precisely to S. Since we have ⌊logK⌋+1 levels we get that the total amount of work is O(log K · S · log S), as required.
12
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 log M ) 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?
Solution: Form the polynomial xv1 + · · · + xvN and use convolution to obtain its square. Drop all powers with coefficient equal to 1. The remaining powers provide the solution, because xv1 xv2 = xv1 +v2 . Note that if v1 ̸= v2 then this product appears with the coefficient at least 2 (once as xv1xv2 and once as xv2 xv1 ; if v1 appears only once, then x2v1 also appears only once, thus also with a coefficient 1. So, because you pick coins without replacement you must drop all powers appearing with coefficient 1.
13. Consider the polynomial
P(x)=(x−ω0 )(x−ω1 )(x−ω2 )...(x−ω63)
64 64 64 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.
Solution:
13
(a)
P(0)=(0−ω0 )(0−ω1 )...(0−ω63) 64 64 64
= (−1)64ω0+1+···+63 64
64×63 =ω2
64
= ω32∗63
64
= ω3263 64
= (−1)63 = −1
(b) The degree of P(x) is 64. The coefficient of the highest degree of x is 1 (there is only one term in the product of degree 64, which is all the x’s multiplied together).
(c) The values at all roots of unity are 0.
(d) Since P(x) is precisely the polynomial whose roots are at the 64th roots of unity, P (x) = x64 − 1, by definition. Note that this is clearly an easier way to solve part (a)!
14. To apply the FFT to the sequence (a0, a1, a2, a3, a4, a5, a6, a7) we apply recur- sively FFT and obtain F F T (a0, a2, a4, a6) and F F T (a1, a3, a5, a7). Proceed- ing further with recursion, we obtain FFT(a0,a4) and FFT(a2,a6) as well as FFT(a1,a5)andFFT(a3,a7). Thus,frombottomup,(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.
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
Solution: In the example given above the indices of (a0, a4, a2, a6, a1, a5, a3, a7) at the leaves are (0, 4, 2, 6, 1, 5, 3, 7) or, in binary,
A3 =(000,100,010,110,001,101,011,111).
Compare this with the sequence (0, 1, 2, 3, 4, 5, 6, 7) written in binary: B3 =
(000,001,010,011,100,101,110,111)andnotethatthebitsoftheith element 14
of sequence A are the mirror image of the bits of the ith element of sequence B. In general, to obtain a sequence Bn+1 of integers in binary in the usual ordering we copy sequence Bn twice adding a zero to the left in the first copy of Bn and 1 to the left in the second copy of Bn. On the other hand, the sequence An+1 contains first all even index terms followed by all odd index terms; thus, recursively, An+1 is obtained from one copy of An with 0 concatenated to each element at its right end followed by another copy of An with 1 concatenated at the right of each element.
15. You are given a sequence
of length n and sequence
A = ⟨a0,a1,...,an−1⟩
B = ⟨1,0,0,...,0,−1⟩
k
(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).
Solution: Since B = ⟨1, 0, . . . , 0, 1⟩, the corresponding polynomial is PB (x) =
k
of length k + 2, where 1 ≤ k ≤ n/4. (a) Compute the DFT of sequence B.
1−xk+1 and
DFT(B) = ⟨P (ω0 ),P (ω1 ),...,P (ωk+1)⟩
B k+2 B k+2 B k+2
= ⟨1 − ω0·(k+1), 1 − ω1·(k+1), . . . , 1 − ω(k+1)·(k+1)⟩
k+2 k+2 k+2
= ⟨0, 1 − ωk+1, 1 − ω2(k+1), . . . , 1 − ω(k+1)2 ⟩
k+2 k+2 k+2
The polynomial corresponding to sequence A is PA(x) = a0 +a1x+a2x2 +...+
an−1xn−1; thus
PA(x)PB(x)=a0 +a1x+...+an−1xn−1 −a0xk+1 −a1xk+2 −a2xk+3 +...+an−1xn−1+k+1
15
16.
We now use the fact that k ≤ n/4 to transform this expression into PA(x)PB(x)=a0 +a1x+a2x2 +...+akxk +(ak+1 −a0)xk+1 +(ak+2 −a1)xk+2+
. . . + (an−1 − an−k−2)xn−1 − an−k−1xn − . . . − an−1xn+k Thus C = A ∗ B is given by
C =⟨a0,a1,...,ak,(ak+1 −a0),(ak+2 −a1),...,(an−1 −an−k−2),−an−k−1, −an−k, . . . − an−2, −an−1⟩
(a) Compute the DFT of the sequence (1, −1, −1, 1) by any method you wish.
(b) Computethelinearconvolutionofsequences(1,−1,−1,1)and(−1,1,1,−1) by any method you wish.
Solution:
(a) DFT of sequence (1, −1, −1, 1) is just the sequence of values of the asso- ciated polynomial P(x) = 1−x−x2 +x3 at the roots of unity of order 4, which are 1,i,−1,−i. Thus P(1) = 1−1−1+1 = 0; P(i) = 1−i−i2+i3 = 1−i−(−1)−i = 2−2i; P(−1) = 1−(−1)−(−1)2 +(−1)3 = 0 and finally P(−i) = 1−(−i)−(−i)2 +(−i)3 = 1+i+1+i = 2+2i. Thus, DF T (1, −1, −1, 1) = (0, 2 − 2i, 0, 2 + 2i).
(b) As defined in lecture slides #2, linear convolution of two sequences is just the sequence of the coefficients of the polynomial which is the product of the two polynomials associated with the two sequences. Thus we form P (x) = 1−x−x2 +x3 and Q(x) = −1+x+x2 −x3 and we simply multiply them by brute force because the polynomials are of such small degree: P(x)Q(x) = −1+2x+x2−4x3+x4+2x5−x6. So linear convolution of these two sequences is (1, −1, −1, 1) ∗ (−1, 1, 1, −1) = (−1, 2, 1, −4, 1, 2, −1).
AssumethatyouaregivenapolynomialP(x)=a0+a1x+a2x2+a3x3 anda 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.
16
17.
Solution: Just note that R(x) = P (x)2 −Q(x)2 = (P (x)−Q(x))(P (x)+Q(x)). Now just compute P (x) − Q(x) and P (x) + Q(x) which are both polynomials of degree 3, so their product can be obtained using only 7 multiplications.
18. Recall that the DFT of a sequence
⟨a0,a1,...,an−1⟩ ⟨P(ω0),P(ω1),P(ω2),...,P(ωn−1)⟩
is the sequence of values
nnnn
oftheassociatedpolynomialP(x)=a0+a1x+a2x2+...+an−1xn−1. Compute directly (i.e., without using the FFT) and maximally simplify the DFT of the following sequences:
(a) ⟨1,0,...,0⟩
n−1
(b) ⟨0,...,0, 1⟩
n−1 (c) ⟨1,...,1⟩
n
Solution:
(a) ⟨1,0,...,0⟩ produces a constant polynomial P(x) = 1. Thus P(ωnk) = 1
n−1
for all k. Consequently, the DFT is equal to ⟨1, 1, . . . , 1⟩.
(b) ⟨ 0, . . . , 0, 1⟩ produces polynomial P (x) = xn−1. Consequently, the DFT
n−1
is equal to
⟨1, ωn−1, ω2(n−1), . . . , ω(n−1)(n−1)⟩ = ⟨1, ωnω−1, ω2nω−2, . . . , ω(n−1)nω−(n−1)⟩ nnnnnnnnn
= ⟨1,ω−1,ω−2,...,ω−(n−1)⟩ nnn
(c) ⟨1,...,1⟩producesthepolynomial
n
P(x)=1+x+x2 +x3 +...+xn−1 = 1−xn 1−x
17
whichis0forallx̸=1because(ωnk)n =(ωn)k =1. Ifx=1then P(x) = 1+...+1 = n. Thus, the DFT of the sequence is equal to ⟨n,0,0,...,0⟩.
18