Algorithms Tutorial 2
Algorithm | mining – 这个题目属于一个Algorithm的代写任务, 是比较有代表性的Algorithm/mining等代写方向
Solutions
Divide and Conquer and polynomial multiplication
- You are given a 2n 2 nboard 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:
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.
- You and a friend find yourselves on a TV game show! The game works as follows. There is ahiddenNNtableA. Each cellA[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 theN cells each containing themaximumvalue in its row. Formally, you need to produce an arrayM[1..N] so thatA[r, M[r]] contains the maximum value in rowrofA, i.e., such thatA[r, M[r]] is the largest integer amongA[r,1], A[r,2],… , A[r, N]. In addition, to win, you should ask at most 2 NdlogNemany 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
then the correct output would beM= [1, 2 , 2 ,4].
Your friend has just had a go, and sadly failed to win the prize because they
askedN^2 many questions which is too many. However, they whisper to you a
hint: they found out thatM isnon-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 mostO(NlogN) many questions that pro-
duces the arrayMcorrectly, 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 determiningM[N/2]first, and see if divide-and-conquer is of
any assistance.
Solution: We first findM[N/2]. We can do this inN questions by simply
exa mining each element in row N/2, and finding the largest one. Suppose
M[N/2] =x. Then, we know for alli < N/2,M[i]xand for allj > N/2,
M[j]x. Thus, we can recurse to solve the same problem on the sub-grids
A[1..(N/2)1][1..x] andA[(N/2) + 1..N][x..N]. It remains to show that this
approach uses at most 2NdlogNequestions.
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
log 2 (N) many recursion calls thus resulting in inspection of at most 2Nlog 2 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
2 Nlog 2 N.
- Given positive integersMandncomputeMnusing onlyO(logn) many mul- tiplications. (15 pts)
Solution:Note that whennis even,Mn= (M
n
(^2) )^2 , and whennis odd,Mn= (M n 21 )^2 M. Hence, we can proceed by divide and conquer. Ifnis even, we recursively computeM n (^2) and then square it. Ifnis odd, we recursively compute M n 21 , square it and then multiply by anotherM. Sincenis (approximately) halved in each recursive call, there are at mostO(logn) recursive calls, and since we perform only one or two multiplications in each recursive call, the algorithm performsO(logn) many multiplications, as required. Alternative Solution: Any positive integernis the sum of a subset of the powers of 2 ({ 1 , 2 , 4 , 8 , 16 , …}). Thus,Mnis the product of a subset of powers of Mwhere the power is a power of 2 ({M, M^2 , M^4 , M^8 , …}). We can obtain these powers ofMinO(logn) time by repeated squaring and then multiply together the appropriate powers to getMn. The appropriate powers to multiply are the powersM^2 i such that theithleast significant bit of the binary representation ofnis 1. For example, to obtainM^11 , the binary representation of 11 is 1011, and hence we should multiply togetherM,M^2 , andM^8.
- Let us define the Fibonacci numbers asF 0 = 0,F 1 = 1 andFn=Fn 1 +Fn 2 for alln2. 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 integersn1.
(b) Hence or otherwise, give an algorithm that findsFninO(logn) time.
Hint: You may wish to refer to Example 1.5 on page 28 of the Review Mate-
rial booklet.
Solution
(a) Whenn= 1 we have
(
Fn+1 Fn
Fn Fn 1
)
=
(
1 1
1 0
)
=
(
1 1
1 0
) 1
so our claim is true forn= 1.
Letk1 be an integer, and suppose our claim holds forn=k(Inductive
Hypothesis). Then
(
1 1
1 0
)k+
=
(
1 1
1 0
)k(
1 1
1 0
)
=
(
Fk+1 Fk
Fk Fk 1
)(
1 1
1 0
)
by the Inductive Hypothesis. Hence
(
1 1
1 0
)k+
=
(
Fk+1+Fk Fk+
Fk+Fk 1 Fk
)
=
(
Fk+2 Fk+
Fk+1 Fk
)
by the definition of the Fibonacci numbers. Hence, our claim is also true
forn=k+ 1, so by induction it is true for all integersn1.
(b) Let
G=
(
1 1
1 0
)
and suppose we knowGx. Then, we can computeG^2 xby simply squaring
Gx, which takesO(1) time. Since it is enough to computeGn, we can do
so by first computingG^2
t
for allt blog 2 nc: we can do this inO(logn)
steps by repeatedly squaringG.
Then, we can consider the base 2 representation ofn: this tells us precisely
whichG^2
t
matrices we should multiply together to obtainGn.
As an alternative (and equivalent) solution, we can proceed by divide and
conquer. To computeGn: ifnis even, recursively computeGn/^2 and square
it inO(1). Ifnis odd, recursively computeG(n1)/^2 , square it and then
multiply by anotherG: this last step also occurs inO(1). Since there are
O(logn) steps of the recursion only, this algorithm runs inO(logn).
- 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 polynomialA(x) of degree 16 and a polynomial B(x) of degree 8 is a polynomialC(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 evaluateA(i) andB(i) for allisuch that 12 i12. Note that this
does not involve any multiplication of two arbitrarily large numbers but only
multiplications of one arbitrarily large number (a coefficient ofA(x) orB(x))
with a constant. Notice that the constant involved can be very large, such as
1216 occurring when we evaluateA(12) = A 0 +A 1 12 +.. .+A 16 1216.
We now perform 25 large number multiplications which produce the values of
the product polynomialC(x) =A(x)B(x) at inputs ranging from12 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 variablesC 0 ,... , C 24 :
{C 0 +C 1 i+C 2 i^2 +.. .+C 24 i^24 =C(i) =A(i)B(i) : 12 i 12 }
Solving such a system expresses the solutions forC 0 ,... , C 24 as a linear com-
bination of values ofC(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 polynomialsA(x) andB(x).
- 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) =a 0 +a 2 x^2 +a 4 x^4 +a 6 x^6 ;Q(x) =b 0 +b 2 x^2 +b 4 x^4 +b 6 x^6 using at
most 7 multiplications of large numbers;
(b) P(x) =a 0 +a 100 x^100 andQ(x) =b 0 +b 100 x^100 with at most 3 multiplica-
tions of large numbers.
Solution:
(a) Note that using the substitutiony=x^2 reducesP(x) toP(y) =a 0 +
a 2 y+a 4 y^2 +a 6 y^3 andQ(x) toQ(y) = b 0 +b 2 y+b 4 y^2 +b 6 y^3. The
productR(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-
ateP(y) andQ(y) at seven values of its argumentx, by lettingx=
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-
efficientsr 0 ,... , r 6 such thatR(x) = r 0 +r 1 x+.. .+r 6 x^6. Thus we
solve the system{
6
j=0rji
j =R(i) : 3 i 3 }. We now form the
polynomialR(x) =r 0 +r 1 x+.. .+r 6 x^6 with thus obtainedrjand finally
substitute backywithx^2 obtainingR(x) =P(x)Q(x).
(b) We use (essentially) the Karatsuba trick:
(a 0 +a 100 x^100 )(b 0 +b 100 x^100 ) =a 0 b 0 + (a 0 b 100 +b 0 a 100 )x^100 +a 100 b 100 x^200
=a 0 b 0 + ((a 0 +a 100 )(b 0 +b 100 )a 0 b 0 a 100 b 100 )x^100 +a 100 b 100 x^200
Note that the last expression involves only three multiplications:a 0 b 0 ,a 100 b 100
and (a 0 +a 100 )(b 0 +b 100 ).
(a) Multiply two complex numbers (a+ b) and (c+ d) (wherea, b, c, dare
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) =acbd+ (bc+ad) =acbd+ ((a+b)(c+d)acbd)
so we need only 3 multiplications:acandbdand (a+b)(c+d).
(a) (a+ b)^2 =a^2 b^2 + 2ab = (a+b)(ab) + (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.
- Assume that you are given a polynomialP(x) =a 0 +a 1 x+a 2 x^2 +a 3 x^3 and a polynomialQ(x) =b 0 +b 1 x+b 2 x^2 +b 3 x^3 whose coefficients can be arbitrarily large numbers. LetR(x) =P(x)^2 Q(x)^2. Compute the coefficients ofR(x) using only 7 large number multiplications.
Solution:Just note thatR(x) =P(x)^2 Q(x)^2 = (P(x)Q(x))(P(x)+Q(x)).
Now just computeP(x)Q(x) andP(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.
- You are given a polynomialP(x) =A 0 +A 1 x^100 +A 2 x^200 whereA 0 , A 1 , A 2 can be arbitrarily large integers. Design an algorithm which squaresP(x) using only 5 large integer multiplications. (15 pts) Solution: Note that using the substitutiony=x^100 reducesP(x) toP(y) = A 0 +A 1 y^1 +A 2 y^2 , and it is clear thatP(y)^2 will have the same coefficients asP(x)^2. The polynomialQ(y) =P(y)^2 is of degree 4 so to uniquely deter- mineQ(y) we need five of its values. Thus, we evaluateQ(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 ofQ(y) by solving the corresponding system of linear equations. After we have found the coefficients ofQ(y), we can substituteyback withx^100 to obtainP(x)^2. Alternative, cleverer solution by a student:Note that
(A 0 +A 1 x^100 +A 2 x^200 )^2 =A^20 +2A 0 A 1 x^100 +(A^21 +2A 0 A 2 )x^200 +2A 1 A 2 x^300 +A^22 x^400
and that
(A 0 +A 1 +A 2 )^2 A^20 A^22 2 A 0 A 1 2 A 1 A 2 =A^21 + 2A 0 A 2
Thus, we only need 5 multiplications of large numbers to computeA^20 , A^22 ,
A 0 A 1 ,A 1 A 2 and (A 0 +A 1 +A 2 )^2 to obtain all the needed coefficients.