CS170 -Homework 3 - Solved

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 demonstrate 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:

                                                      ,

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.

(a)    Define

 

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

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

 

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  ) 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).

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(nlogn) 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(mlogm) 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)).