Assignment 2
Due date Tuesday Jun 30, 2020 at 9am
You have five problems, marked out of a total of 100 marks.
submissions will be checked for plagiarism!
1. Given positive integers M and n compute Mn using only O(log n) many
multiplications. (15 pts)
Hint: You might want to write n in binary, i.e., as n = 2k1 + 2k2 + 2km
where k1 > k2 > . . . km and k1 = blog2 nc;
This involves at most blog2 nc multiplications. So it is enough to compute
all of m2
j
for all 1 ≤ j ≤ blog2 nc with at most blog2 nc multiplications.
To do that, use repeated squaring.
2. You are given a polynomial P(x) = A0+A1x
100+A2x
200 where A0, A1, A2
can be arbitrarily large integers. Design an algorithm which squares
P(x) using only 5 large integer multiplications. (15 pts)
Hint: Use substitution y = x
100, square the resulting polynomial and
then substitute back y with x
100
.
3. Assume you are given a map of a straight sea shore of length 100n meters
as a sequence on 100n numbers such that Ai
is the number of fish
between i
th meter of the shore and (i + 1)th meter, 0 ≤ i ≤ 100n − 1.
You also have a net of length n meters but unfortunately it has holes
in it. Such a net is described as a sequence N of n ones and zeros,
where 0’s denote where the holes are. If you throw such a net starting
at meter k and ending at meter k + n, then you will catch only the fish
in one meter stretches of the shore where the corresponding bit of the
net is 1. Find the spot where you should place the left end of your net
in order to catch the largest possible number of fish using an algorithm
which runs in time O(n log n). (30 pts)
Hint: Let N0
be the net sequence N in the reverse order; compute the
sequence A ∗ B0
; see the figure and then look where the largest value of
this sequence is.
1
4. (a) Compute the convolution h1, 0, 0, . . . , 0
| {z }
k
, 1i ∗ h1, 0, 0, . . . , 0
| {z }
k
, 1i (10
pts)
(b) Compute the DFT of the sequence h1, 0, 0, . . . , 0
| {z }
k
, 1i (10 pts)
Hint: Find the polynomial associated with the sequence h1, 0, 0, . . . , 0
| {z }
k
, 1i
and then square it to get (a) and evaluate it at all roots of unity of order
k + 2 to get (b).
5. Find the sequence x satisfying x ∗ h1, 1, −1i = h1, 0, −1, 2, −1i.(20 pts)
Hint: Clearly, x is a sequence of length 5+1-3=3; write it as ha, b, ci.
Find the polynomials which correspond to sequences x and h1, 1, −1i
and multiply them. Equate the coefficients of the product polynomial
with the terms of the sequence h1, 0, −1, 2, −1i.