These are rough, personal lecture notes handwritten by Erik Demaine
used during lecture. Their primary purpose is for reading/review by students
of the class. They supplement
scribe
notes prepared by students.
Accessibility
- Lecture 3: Binary search trees: Splay trees, bounds, dynamic optimality conjecture -- pages 1, 2, 3, 4, 5
- Lecture 4: Binary search trees: Key-independent optimality and O(lg lg n)-competitive
Tango trees, via Wilber lower bounds -- pages 1, 2, 3, 4, 5, 6
- Lecture 5: Dynamic graphs: dynamic trees via link-cut trees -- pages 1, 2, 3, 4
- Lecture 6: Dynamic graphs: Euler-tour trees, dynamic undirected graph problems,
dynamic connectivity in O(lg2 n) -- pages 1, 2, 3, 4, 5
- Lecture 7: Dynamic graphs: Ω(lg n) lower bound on dynamic connectivity -- pages 1, 2, 3, 4, 5
- Lecture 8: Dynamic graphs: dynamic directed graphs and shortest paths,
O(n2) worst-case dynamic transitive closure,
dynamic matrices -- pages 1, 2, 3, 4
- Lecture 9: Integers: Models, predecessor problem, van Emde Boas, y-fast trees -- pages 1, 2, 3, 4, 5
- Lecture 10: Integers: Fusion trees -- pages 1, 2, 3, 4, 5
- Lecture 11: Integers: Predecessor lower bounds via round elimination -- pages 1, 2, 3, 4, 5
- Lecture 12: Integers: Tight upper and lower bounds for predecessor via message compression -- pages 1, 2, 3, 4, 5
- Lecture 13: Integers: Sorting in linear time for
w = Ω(lg2+ε n) -- pages 1, 2, 3, 4, 5
- Lecture 14: Integers: Equivalence between sorting and priority queues -- pages 1, 2
- Lecture 15: Range queries and trees: Static LCA, RMQ -- pages 1, 2
- Lecture 16: Range queries and trees: tree decompositions, marked ancestor upper bound,
decremental connectivity in trees -- pages 1, 2, 3, 4
- Lecture 17: Range queries and trees: Marked ancestor lower bound -- pages 1, 2, 3
- Lecture 18: Strings: Suffix trees, "3" construction, document retrieval -- pages 1, 2, 3, 4
- Lecture 19: Strings: Approximate string matching, searching with wild cards,
level ancestor problem -- pages 1, 2, 3, 4, 5
- Lecture 21: Succinct data structures: rank, select, binary tries -- pages 1, 2, 3, 4, 5
- Lecture 22: Succinct data structures: compact suffix arrays and trees -- pages 1, 2, 3, 4
- Lecture 23: External memory / cache-oblivious: cache-oblivious B-trees -- pages 1, 2, 3, 4, 5
- Lecture 24: External memory / cache-oblivious: Ordered file maintenance, list labeing
and order queries, cache-oblivious priority queues -- pages 1, 2, 3, 4, 5
- Lecture 25: Student presentations I -- pages 1, 2
- Lecture 26: Student presentations II -- pages 1, 2