6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine TAs: Timothy Kaler, Aaron Sidford

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

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]

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.