6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine     TAs: Timothy Kaler, Aaron Sidford


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

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

[+] Integer lower bounds + sorting (L13 + L14)

These two lectures had a record number of questions, though this time the confusion was generally about how all the parts fit together at the high level, rather than the low-level details. So we'll be reviewing both main topics at a high level, skipping the messy details:

  • Predecessor lower bound / round elimination and how it works (this is tough stuff, so don't feel bad!)
  • Packed sorting / signature sorting and how they recurse
Feel free to bring any specific questions you might have.

In addition, we'll have a neat new solved problem about an alternative way to do packed sorting. (Assuming it works out how we think it does, it might even be publishable... let us know whether you want to write it up as a final project!)

And we had a very nice open problem based on pset 6, but it may have already been solved...! We'll see!

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

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

Lecture notes, page 1/4[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.