Lecture 14: 02/15/2012

Now that we’ve wrapped up the FFT and polynomial multiplication, we can focus on applying it to the 3SUM problem.

A slight modification of the 3SUM problem, which we can call the average, asks if there is a length 3 arithmetic progression in an array. Alternatively, we can ask if there are three evenly spaced “1” bits in a binary number.

We model a number Z written in binary as a polynomial A(x) = b_0 + b_1 x + b_2 x^2 + … + b_{k-1} x^{k-1} where k = log Z and b_i = 1 if the ith bit of Z is a “1” and b_i = 0 otherwise.

Now, let’s look at the convolution of A with itself, i.e., [A(x)]^2 = \sum_{i=0}^{2k-2} c_i x^i where c_i = \sum_{j=0}^{i} b_j b_{i-j} = \sum_{j+l=i} b_j b_l.

To examine three evenly spaced bits, we can look at the endpoints of the of the sequence, or the middle of the sequence. Hence, if the mth bit of Z is a 1, we can look at c_{2m} and check if its bigger than 1. It will be at least 1, since the x_m term in A is multiplied by itself. If it is bigger than 1, then there is a pair of indices that denote the endpoints of an evenly spaced sequence of 1’s with the mth bit as the middle.

At the end, we wrapped up by discussing the FFT in regards to the primitive root of unity and how feasible it is to find it for a certain field.

Don’t forget that the midterm is next week on Wednesday, so study hard!

On friday, Professor Blum will wrap up the last part of the Union-Find analysis and start on Splay trees. Please make sure to read these relevant sections in Kozen before the next lecture.


Lecture 13: 02/13/2012

Here’s a link to the Path Compression paper handed out at the beginning of lecture, in case you didn’t get a copy:

Prof. Rudich got through the rest of the FFT today, covering the divide-and-conquer approach used to compute polynomials on the way down in the recursion, similar to merge sort. On the way back up, we compose a polynomial p_1 of odd powers and p_2 of even powers to get p = p_1 + x*p_2.

Unfortunately, we didn’t get to cover applications of the FFT to 3SUM, but we’ll definitely get to that at the beginning of next lecture.

Don’t forget to work on that exam question due on Wednesday. If you don’t have anyone to spend Valentine’s day with, why not spend it with Algo HW :-/

Lecture 12: 02/10/2012

Today’s topic was the FFT. We didn’t get all the way through it, but Prof. Rudich will finish up on Monday. We started with definitions and assumptions about the ring we work with, but as a running example we used the simple ring Z_11. The key points of the FFT are that if we convert between coefficients and the sample point representation of a polynomial, we can compute the convolution by performing a linear number of multiplications.

The bulk of the lecture dealt with which sample points should we use: the nth roots of unity. They have some really nice properties that make the FFT work in sub-quadratic time.

We’ll finish discussing the matrix of the roots and its inverse on Monday. Please try to review the lecture in Kozen and bring some good questions to lecture.

Have a great weekend!