首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Tsp课程作业代写、代做algorithms留学生作业、代做java，C/C 2020-06-23
- Kit107留学生作业代做、C++编程语言作业调试、Data课程作业代写、代 2020-06-23
- Sta302h1f作业代做、代写r课程设计作业、代写r编程语言作业、代做da 2020-06-22
- 代写seng 474作业、代做data Mining作业、Python，Ja 2020-06-22
- Cmpsci 187 Binary Search Trees 2020-06-21
- Comp226 Assignment 2: Strategy 2020-06-21
- Math 504 Homework 12 2020-06-21
- Math4007 Assessed Coursework 2 2020-06-21
- Optimization In Machine Learning Assig... 2020-06-21
- Homework 1 – Math 104B 2020-06-20
- Comp1000 Unix And C Programming 2020-06-20
- General Specifications Use Python In T... 2020-06-20
- Comp-206 Mini Assignment 6 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Mech 203 – End-Of-Semester Project 2020-06-20
- Ms980 Business Analytics 2020-06-20
- Cs952 Database And Web Systems Develop... 2020-06-20
- Homework 4 Using Data From The China H... 2020-06-20
- Assignment 1 Build A Shopping Cart 2020-06-20