data留学生代做、代写algorithm、代写Java，c/c++语言、Python编程代做

日期：2020-06-30 11:11

Assignment 2

Due date Tuesday Jun 30, 2020 at 9am

You have five problems, marked out of a total of 100 marks.

NOTE: Your solutions must be typed, machine readable .pdf files. All

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.

2