xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-CS 170

时间：2021-02-05

CS 170, Spring 2021 Homework 3 A. Chiesa & J. Demmel

CS 170 Homework 3

Due 2/09/2021, at 10:00 pm

1 Study Group

List the names and SIDs of the members in your study group. If you have no collaborators,

write “none”.

2 Modular Fourier Transform

Fourier transforms (FT) have to deal with computations involving irrational numbers which

can be tricky to implement in practice. Motivated by this, in this problem you will demon-

strate how to do a Fourier transform in modular arithmetic, using modulo 5 as an example.

(a) There exists ω ∈ {0, 1, 2, 3, 4} such that ω are 4th roots of unity (modulo 5), i.e., solutions

to z4 = 1. When doing the FT in modulo 5, this ω will serve a similar role to the primitive

root of unity in our standard FT. Show that {1, 2, 3, 4} are the 4th roots of unity (modulo

5). Also show that 1 + ω + ω2 + ω3 = 0 (mod 5) for ω = 2.

(b) Using the matrix form of the FT, produce the transform of the sequence (0, 1, 0, 2) modulo

5; that is, multiply this vector by the matrix M4(ω), for the value ω = 2. Be sure to

explicitly write out the FT matrix you will be using (with specific values, not just powers

of ω). In the matrix multiplication, all calculations should be performed modulo 5.

(c) Write down the matrix necessary to perform the inverse FT. Show that multiplying by

this matrix returns the original sequence. (Again all arithmetic should be performed

modulo 5.)

(d) Now show how to multiply the polynomials 2x2 + 3 and −x+ 3 using the FT modulo 5.

3 Inverse FFT

Recall that in class we defined Mn, the matrix involved in the Fourier Transform, to be the

following matrix:

Mn =

1 1 1 . . . 1

1 ω ω2 . . . ωn−1

...

...

...

. . .

...

1 ωn−1 ω2(n−1) . . . ω(n−1)(n−1)

,

where ω is a primitive n-th root of unity.

For the rest of this problem we will refer to this matrix as Mn(ω) rather than Mn. In this

problem we will examine the inverse of this matrix.

1

CS 170, Spring 2021 Homework 3 A. Chiesa & J. Demmel

(a) Define

Mn(ω

−1) =

1 1 1 . . . 1

1 ω−1 ω−2 . . . ω−(n−1)

...

...

...

. . .

...

1 ω−(n−1) ω−2(n−1) . . . ω−(n−1)(n−1)

Recall that ω−1 = 1/ω = ω¯ = exp(−2pii/n).

Show that 1nMn(ω

−1) is the inverse of Mn(ω), i.e. show that

1

n

Mn(ω

−1)Mn(ω) = I

where I is the n×n identity matrix – the matrix with all ones on the diagonal and zeros

everywhere else.

(b) Let A be a square matrix with complex entries. The conjugate transpose A† of A is given

by taking the complex conjugate of each entry of AT . A matrix A is called unitary if

its inverse is equal to its conjugate transpose, i.e. A−1 = A†. Show that 1√

n

Mn(ω) is

unitary.

(c) Suppose we have a polynomial C(x) of degree at most n − 1 and we know the values

of C(1), C(ω), . . . , C(ωn−1). Explain how we can use Mn(ω−1) to find the coefficients of

C(x).

2

CS 170, Spring 2021 Homework 3 A. Chiesa & J. Demmel

4 Triple sum

We are given an array A[0..n− 1] with n elements, where each element of A is an integer in

the range 0 ≤ A[i] ≤ n (the elements are not necessarily distinct). We would like to know if

there exist indices i, j, k (not necessarily distinct) such that

A[i] +A[j] +A[k] = n

Design an O(n log n) time algorithm for this problem. Note that you do not need to actually

return the indices; just yes or no is enough.

Please give a 3-part solution to this problem.

5 Searching for Viruses

Sherlock Holmes is trying to write a computer antivirus program. He thinks of computer

RAM as being a binary string s2 of length m, and a virus as being a binary string s1 of

length n < m. His program needs to find all occurrences of s1 in s2 in order to get rid of the

virus. Even worse, though, these viruses are still damaging if they differ slightly from s1. So

he wants to find all copies of s1 in s2 that differ in at most k locations for arbitrary k ≤ n.

(a) Give a O(nm) time algorithm for this problem.

(b) Give a O(m logm) time algorithm for any k.

You do not need a 3-part solution for either part. Instead, describe the algorithms clearly

and give an analysis of the running time.

6 FFT Coding

This semester, we are trying something new: questions which involve coding.

This link will take you to a python notebook, hosted on the Berkeley datahub, in which

you will implement three functions (FFT, calc nth root, and poly multiply) to investigate

how FFT works. Once you have finished, download a PDF of your completed notebook via

File → Download as → PDF via HTML, and append the downloaded pdf to the rest of your

homework submission. Be careful when selecting pages on gradescope.

Note: Datahub does not guarantee 100% reliability when you save your notebook, and

recommends downloading a local copy occasionally to backup progress (via File→ Download

as → Notebook (.ipynb)).

3

学霸联盟

CS 170 Homework 3

Due 2/09/2021, at 10:00 pm

1 Study Group

List the names and SIDs of the members in your study group. If you have no collaborators,

write “none”.

2 Modular Fourier Transform

Fourier transforms (FT) have to deal with computations involving irrational numbers which

can be tricky to implement in practice. Motivated by this, in this problem you will demon-

strate how to do a Fourier transform in modular arithmetic, using modulo 5 as an example.

(a) There exists ω ∈ {0, 1, 2, 3, 4} such that ω are 4th roots of unity (modulo 5), i.e., solutions

to z4 = 1. When doing the FT in modulo 5, this ω will serve a similar role to the primitive

root of unity in our standard FT. Show that {1, 2, 3, 4} are the 4th roots of unity (modulo

5). Also show that 1 + ω + ω2 + ω3 = 0 (mod 5) for ω = 2.

(b) Using the matrix form of the FT, produce the transform of the sequence (0, 1, 0, 2) modulo

5; that is, multiply this vector by the matrix M4(ω), for the value ω = 2. Be sure to

explicitly write out the FT matrix you will be using (with specific values, not just powers

of ω). In the matrix multiplication, all calculations should be performed modulo 5.

(c) Write down the matrix necessary to perform the inverse FT. Show that multiplying by

this matrix returns the original sequence. (Again all arithmetic should be performed

modulo 5.)

(d) Now show how to multiply the polynomials 2x2 + 3 and −x+ 3 using the FT modulo 5.

3 Inverse FFT

Recall that in class we defined Mn, the matrix involved in the Fourier Transform, to be the

following matrix:

Mn =

1 1 1 . . . 1

1 ω ω2 . . . ωn−1

...

...

...

. . .

...

1 ωn−1 ω2(n−1) . . . ω(n−1)(n−1)

,

where ω is a primitive n-th root of unity.

For the rest of this problem we will refer to this matrix as Mn(ω) rather than Mn. In this

problem we will examine the inverse of this matrix.

1

CS 170, Spring 2021 Homework 3 A. Chiesa & J. Demmel

(a) Define

Mn(ω

−1) =

1 1 1 . . . 1

1 ω−1 ω−2 . . . ω−(n−1)

...

...

...

. . .

...

1 ω−(n−1) ω−2(n−1) . . . ω−(n−1)(n−1)

Recall that ω−1 = 1/ω = ω¯ = exp(−2pii/n).

Show that 1nMn(ω

−1) is the inverse of Mn(ω), i.e. show that

1

n

Mn(ω

−1)Mn(ω) = I

where I is the n×n identity matrix – the matrix with all ones on the diagonal and zeros

everywhere else.

(b) Let A be a square matrix with complex entries. The conjugate transpose A† of A is given

by taking the complex conjugate of each entry of AT . A matrix A is called unitary if

its inverse is equal to its conjugate transpose, i.e. A−1 = A†. Show that 1√

n

Mn(ω) is

unitary.

(c) Suppose we have a polynomial C(x) of degree at most n − 1 and we know the values

of C(1), C(ω), . . . , C(ωn−1). Explain how we can use Mn(ω−1) to find the coefficients of

C(x).

2

CS 170, Spring 2021 Homework 3 A. Chiesa & J. Demmel

4 Triple sum

We are given an array A[0..n− 1] with n elements, where each element of A is an integer in

the range 0 ≤ A[i] ≤ n (the elements are not necessarily distinct). We would like to know if

there exist indices i, j, k (not necessarily distinct) such that

A[i] +A[j] +A[k] = n

Design an O(n log n) time algorithm for this problem. Note that you do not need to actually

return the indices; just yes or no is enough.

Please give a 3-part solution to this problem.

5 Searching for Viruses

Sherlock Holmes is trying to write a computer antivirus program. He thinks of computer

RAM as being a binary string s2 of length m, and a virus as being a binary string s1 of

length n < m. His program needs to find all occurrences of s1 in s2 in order to get rid of the

virus. Even worse, though, these viruses are still damaging if they differ slightly from s1. So

he wants to find all copies of s1 in s2 that differ in at most k locations for arbitrary k ≤ n.

(a) Give a O(nm) time algorithm for this problem.

(b) Give a O(m logm) time algorithm for any k.

You do not need a 3-part solution for either part. Instead, describe the algorithms clearly

and give an analysis of the running time.

6 FFT Coding

This semester, we are trying something new: questions which involve coding.

This link will take you to a python notebook, hosted on the Berkeley datahub, in which

you will implement three functions (FFT, calc nth root, and poly multiply) to investigate

how FFT works. Once you have finished, download a PDF of your completed notebook via

File → Download as → PDF via HTML, and append the downloaded pdf to the rest of your

homework submission. Be careful when selecting pages on gradescope.

Note: Datahub does not guarantee 100% reliability when you save your notebook, and

recommends downloading a local copy occasionally to backup progress (via File→ Download

as → Notebook (.ipynb)).

3

学霸联盟