Algorithms Tutorial 2 Solutions
Divide and Conquer and polynomial multiplication
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. Each dominoe can be rotated.
Solution: We proceed by a divide and conquer recursion; thus, we split the board into 4 equal parts:
1
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.
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 2N⌈logN⌉ many questions. For example, if the hidden grid looks like this:
Column 1 Column 2 Column 3 Column 4 Row1 10 5 8 3 Row2 1 9 7 6 Row3 -3 4 -1 0 Row4 -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).
2
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. Additional exercise: using the above reasoning try to find a bound for the total number of cells investigated which is sharper than 2N log2 N.
3. Given positive integers M and n compute Mn using only O(logn) many mul- tiplications. (15 pts)
3
Solution: Note that when n is even, Mn = (M n2 )2, and when n is odd, Mn = 2
(M n−1 )2 × M . Hence, we can proceed by divide and conquer. If n is even, we n
recursively compute M 2 and then square it. If n is odd, we recursively compute n−1
M 2 , square it and then multiply by another M. Since n is (approximately) halved in each recursive call, there are at most O(logn) recursive calls, and since we perform only one or two multiplications in each recursive call, the algorithm performs O(log n) many multiplications, as required.
Alternative Solution: Any positive integer n is the sum of a subset of the powers of 2 ({1, 2, 4, 8, 16, …}). Thus, M n is the product of a subset of powers of M wherethepowerisapowerof2({M,M2,M4,M8,…}). Wecanobtainthese powers of M in O(log n) time by repeated squaring and then multiply together the appropriate powers to get Mn. The appropriate powers to multiply are the powers M2i such that the ith least significant bit of the binary representation of n is 1. For example, to obtain M11, the binary representation of 11 is 1011, and hence we should multiply together M, M2, and M8.
4. 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 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 Mate- rial” booklet.
Solution
(a) Whenn=1wehave
FF=10 n n−1
Fn+1 Fn 1 1 FF=10
1 11 =10
n
n−1
4
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. (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).
5. 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
5
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 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).
6. 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
6
coefficients, by solving the corresponding system of linear equation in co- efficients r0,…,r6 such that R∗(x) = r0 + r1x + … + r6x6. Thus we solve the system {6j=0 rjij = R∗(i) : −3 ≤ i ≤ 3}. We now form the polynomialR∗(x)=r0+r1x+…+r6x6 withthusobtainedrj andfinally 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). 7.
(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.
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.
8. 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.
7
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 as explained in question 5 in this tutorial.
9. You are given a polynomial P (x) = A0 + A1x100 + A2x200 where A0, A1, A2 can be arbitrarily large integers. Design an algorithm which squares P(x) using only 5 large integer multiplications. (15 pts)
Solution: Note that using the substitution y = x100 reduces P(x) to P∗(y) = A0 + A1y1 + A2y2, and it is clear that P ∗(y)2 will have the same coefficients as P(x)2. The polynomial Q∗(y) = P∗(y)2 is of degree 4 so to uniquely deter- mine Q∗(y) we need five of its values. Thus, we evaluate Q∗(y) at five values: −2, −1, 0, 1, and 2 (this is where the 5 large integer multiplications occur). Then, using these five values, we obtain the coefficients of Q∗(y) by solving the corresponding system of linear equations. After we have found the coefficients of Q∗(y), we can substitute y back with x100 to obtain P(x)2. Alternative, cleverer solution by a student: Note that
(A0+A1x100+A2x200)2 = A20+2A0A1x100+(A21+2A0A2)x200+2A1A2x300+A2x400 and that
(A0 +A1 +A2)2 −A20 −A2 −2A0A1 −2A1A2 =A21 +2A0A2
Thus, we only need 5 multiplications of large numbers to compute A20, A2,
A0A1, A1A2 and (A0 + A1 + A2)2 to obtain all the needed coefficients.
8