[SOLVED] COMP9101 Homework2

1. Given positive integers M and n compute Mⁿ using only O(logn) many multiplications.
2. You are given a polynomial P(x) = A₀+A₁x¹⁰⁰+A₂x²⁰⁰ where A₀,A₁,A₂ can be arbitrarily large integers. Design an algorithm which squares P(x) using only 5 large integer multiplications.
3. Assume you are given a map of a straight sea shore of length 100n meters as a sequence on 100n numbers such that A_i 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(nlogn).

Hint: Let N⁰ be the net sequence N in the reverse order; look at the sequence A ∗ B⁰; see the figure.

4. (a) Compute the convolution

pts)

(b) Compute the DFT of the sequence

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