6.851: Advanced Data Structures (Spring'14)

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

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!