6.897: Advanced Data Structures (Spring 2005)

Prof. Erik Demaine

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(lg² 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(n²) 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
  • [Raman 1995] [page 4]

• Lecture 13: Integers: Sorting in linear time for w = Ω(lg^2+ε 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