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
adona.iosif AT gmail

Don’t forget to work on the homework! The comments section is a good place to start, but the TA office hours are also good.

Have a great weekend!

Lecture 2: 01/18/2012

Here’s the second lecture of the year. We went over the (“easy”) set intersection from Monday’s lecture in more detail. Most questions dealt with the lower bound.

Lecture 1: 01/16/2012

Pictures of the first lecture of the year. Feel free to comment on or discuss lecture material in the comment section.