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