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













































































































































































































学霸联盟