1. Persistent Data Structures
1:23:432. Retroactive Data Structures
1:18:393. Geometric Structures I
1:19:354. Geometric Structures II
1:22:095. Dynamic Optimality I
1:22:446. Dynamic Optimality II
1:23:317. Memory Hierarchy Models
1:22:548. Cache-Oblivious Structures I
1:27:21Lecture 9: Cache-Oblivious Structures II (6.851)
1:24:38Lecture 10: Dictionaries (6.851)
1:23:28Lecture 11: Integer Models (6.851)
1:21:15Lecture 12: Fusion Trees (6.851)
1:24:09Lecture 13: Integer Lower Bounds (6.851)
1:22:10Lecture 14: Sorting in Linear Time (6.851)
1:24:03Lecture 15: Static Trees (6.851)
1:23:00Lecture 16: Strings (6.851)
1:24:30Lecture 17: Succinct Structures I (6.851)
1:20:11Lecture 18: Succinct Structures II (6.851)
1:24:05Lecture 19: Dynamic Graphs I (6.851)
1:14:44Lecture 20: Dynamic Graphs II (6.851)
1:24:47Lecture 21: Dynamic Connectivity Lower Bound (6.851)
1:22:18Lecture 22: History of Memory Models (6.851)
59:245. Dynamic Optimality I
This lecture introduces the concept of dynamic optimality in the context of binary search trees, exploring analytic bounds, the structure of splay trees, a geometric perspective on their performance, and greedy algorithms for dynamic tree operations.
MIT 6.851 Advanced Data Structures, Spring 2012
View the complete course: http://ocw.mit.edu/6-851S12
Instructor: Erik Demaine
Seminar notes & discussion
No public seminar notes on this lecture yet.