1. Given positive integers M and n compute Mn using only O(logn) many multiplications.
2. 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)
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 ith 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(nlogn). (30 pts)
Hint: Let N0 be the net sequence N in the reverse order; look at the sequence A ∗ B0; see the figure.
4. (a) Compute the convolution
pts)
(b) Compute the DFT of the sequence (10 pts)
5. Find the sequence x satisfying x∗h1,1,−1i = h1,0,−1,2,−1i.(20 pts) Hint: what polynomials correspond to the given sequences?
1
