6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine     TAs: Timothy Kaler, Aaron Sidford

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

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

[+] Dynamic optimality (L05 + L06): why geometry represents binary search trees. Problems: making keys distinct, separation between BST and pointer-machine models.

This class reviews the most-asked-about aspect of "the geometry of binary search trees": why do arborally satisfied point sets really correspond to binary search tree data structures? I'll do a worked example for the offline transformation, which will help explain the online transformation too.

Then we have a couple solved and a lot of unsolved problems. Please review the latter and don't review the former. One open problem may already be solved... wow!

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

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

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