Lecture notes, page 1/11 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/11 • [previous page] • [next page] • [PDF]
| [+] Dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm | ||||
| Have
you ever wondered how to represent a binary search tree on n nodes as
a set of n points in 2D? Today's lecture will reveal a surprising new
(2009) such connection, which provides an approach to tackling the
venerable dynamic optimality conjecture.
The dynamic optimality conjecture is one of the oldest and biggest open problems in data structures, asking a fundamental question: is there one best binary search tree? Traditional wisdom is that “splay trees” are such a tree (up to constant factors), but we'll see a new “greedy” tree data structure that we think is more obviously best—though we still can't prove it. Dynamic optimality remains an active and exciting area of research, and this lecture and the next focus on the current state-of-the-art. | ||||
|
Lecture notes, page 1/11 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/11 • [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.