6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine     TAs: Timothy Kaler, Aaron Sidford

[Home] [Lectures] [Assignments] [Project] [Open Problems] [Piazza]

Class 7 Video     [previous] [next] [completion form]

[+] Integer predecessor (L11 + L12)

In this class, we'll review the approximate sketch part of fusion trees, as this seemed to generate the most confusion.

The solved problem will be to take the wrong theorem and proof in lecture, figure out what's wrong with the proof, and find the correct theorem. Ten points for Gryffindor if you can find the bug before I announce it in class. :-) [It survived over a decade before anyone found it...]

A new open problem has been posted. It might be tough, but we have other problems to work on too. (And we have a really good open problem for next class, after spring break, based on this week's problem set!)

[The video still needs to be recorded or encoded. Stay tuned!]

Lecture notes, page 1/2[previous page][next page][PDF]

Lecture notes, page 1/2[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.