# Lecture 15: 02/17/2012

Howdy, Ya’ll. Unfortunately, I couldn’t make it to lecture so I can’t summarize everything that happened but I was there in spirit.

This was the last lecture on Union Find so make sure you review all of the notes as well as Kozen before the exam. I didn’t know my problem would be presented in lecture but I hope you guys liked it. I thought it was cool to see that in general, k-SUM isn’t necessarily O(n^{k-1}). I believe O(n^{\ceil{\frac{k+1}{2}}}) is the best known upper bound.

Have a great weekend!

# 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 4: 01/23/2012

Today’s lecture was about 3SUM as well as the two easier problems (Set Intersection and Search in a Doubly Sorted Array). We discussed ideas for finding good bounds for 3SUM. We talked a bit about Binomial Heaps at the beginning.

*Remember the HW is due Wednesday.

Also, there’s a new homework assignment for next week:
Construct a min-heap in O(n) time.

We’ll start with Binomial Heaps on Wednesday so try to review the lecture in Kozen before the next class.

Good luck guys!

# Lecture 3: 01-20-2012

Here are the pictures from today’s lecture. We recalled the 3SUM problem form the homework (due Wednesday, mind you) and looked at the search in a doubly sorted matrix as a hint for 3SUM. In that problem, we gave an algorithm for the upper bound and gave an argument for the lower bound. It turns out these bounds are tight.

TAs:
William MacRae: F 11:30-12:30 GHC 5208
wmacrae AT andrew
Adona Iosif: M 1:00-2:00 GHC 8221