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.

Next week, we start with Splay Trees. Please make sure to review the chapter in Kozen. Don’t forget about the midterm either.

Have a great weekend!

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 11: 02/08/2012

Unfortunately, we didn’t get to hear about 3SUM today but its good to keep it in the back of your mind.

A great brainstorming session today. We came up with some really interesting problems that might show up on our midterm. Try to think about these or similar problems when writing up your problem for next week’s HW.

Finally, we discussed how the non-linear runtime of Union Find comes about.

Try to cover some of the lemmas in the Analysis of Union-Find chapter in Kozen before next lecture.

Lecture 10: 02/06/2012

We got through most of Union-Find today. The idea is to represent disjoint sets as trees, with a canonical element, i.e. the representative of that set, as the root. The important heuristics for union and find are union-by-rank and path compression, respectively.

Union-by-rank always makes the smaller tree a subtree of the larger one.

Path compression is based on the principle that if we’ve done some work, say O(lg n), then we shouldn’t have any problem with doing it again, since that’s still O(lg n). In that case, when we do a find, it might take a long time to find the root of the tree, but then we go back and change all the parent pointers in the path to the root of the tree. That way, any future finds are shorter.

We wrapped up with a couple exercises that help explain why the complexity of Union-Find isn’t exactly linear. Make sure to think about these since we’re probably going to talk about them later in the week.

Don’t forget that HW3 is due next lecture at the start of class.

Next time, Professor Steven Rudich will lecture on the 3SUM problem. Please make sure to read the chapter on the Fast Fourier Transform (FFT) in Kozen before the next lecture.

Lecture 9: 02/03/2012

A little bit on Fibonacci heaps today at the beginning. We covered Cascading cuts in a Fibonacci tree.

The real meat of the lecture was supposed to be on Kruskal’s Algorithm and the Union-Find algorithm.

We described the Ackermann function, as well as the inverse Ackermann function, in motivation of deriving the run-time of Union-Find, which runs in O(n*a(n)). We didn’t get very far into describing Kruskal’s algorithm so we’ll the algorithm, as well as the analysis of Union-Find next time.

Please make sure to read over Kruskal’s Algorithm, as well as the Union-Find chapters in Kozen before the next lecture.