6.851: Advanced Data Structures (Spring'14)
Prof. Erik Demaine TAs: Timothy Kaler, Aaron Sidford
Geometric (L03 + L04):
full persistence amortization fix, fractional cascading example,
3D orthogonal range searching top-down view,
kinetic data structures survey.
Problems: kinetic heap improved upper bound and tightness.
This class covers the following topics:
Again, solved problems are posted but please don't think about them until class.
Unsolved problems are posted too — please think about them.
- Full persistence amortization: a brief on fixing what was broken last class
- Fractional cascading: a worked example to see how it really works
- 3D orthogonal range searching: a top-down presentation to clarify
- Kinetic data structures survey: a more-than-0 minute coverage of the last page of notes from Lecture 4
- Cool solved and unsolved problems about kinetic data structures
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,