6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine     TAs: Timothy Kaler, Aaron Sidford


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

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

[+] 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:

  • 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
Again, solved problems are posted but please don't think about them until class. Unsolved problems are posted too — please think about them.
[The video still needs to be recorded or encoded. Stay tuned!]

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

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