6.897: Advanced Data Structures (Spring 2003)

Prof. Erik Demaine

Scribe Notes

• Lecture 1: Fixed-universe successor problem, van Emde Boas
  Date: Monday, February 10, 2003
  Scribe: Shantonu Sen
  [PostScript] [PDF]

• Lecture 2: More van Emde Boas, reducing space, dynamic perfect hashing, y-fast trees, transdichotomous RAM
  Date: Wednesday, February 12, 2003
  Scribe: Jeff Lindy
  [PostScript] [PDF]

• Lecture 3: RAMBO model, constant-time RAMBO van Emde Boas, finding least-significant 1-bit, decision-tree model and lg lower bound
  Date: Wednesday, February 19, 2003
  Scribe: Sayan Mitra
  [PostScript] [PDF]

• Lecture 4: Fusion trees
  Date: Monday, February 24, 2003
  Scribe: Ben Leong
  [PostScript] [PDF]

• Lecture 5: More fusion trees; self-organizing data structures, move-to-front, static optimality
  Date: Wednesday, February 26, 2003
  Scribe: Chris Collier
  [PostScript] [PDF]

• Lecture 6: Dynamic optimality of move-to-front, omniscient Order-by-Next-Request beats online algorithms
  Date: Monday, March 3, 2003
  Scribe: Patrick Lam and Ilya Shlyakhter
  [PostScript] [PDF]

• Lecture 7: Entropy bound of Order-by-Next-Request, optimal binary search trees, self-adjusting trees, splay trees, bounds
  Date: Wednesday, March 5, 2003
  Scribe: Sid Sen
  [PostScript] [PDF]

• Lecture 8: Unified property, working-set structure, unified structure
  Date: Monday, March 10, 2003
  Scribe: Lance Anderson and William Kwong
  [PostScript] [PDF]

• Lecture 9: More unified structure, key-independent optimality, Wilber's lower bound, Munro's offline binary search tree
  Date: Wednesday, March 12, 2003
  Scribe: Cristian Cadar and Alexander Andoni
  [PostScript] [PDF]

• Lecture 10: String matching; suffix trees, tries, finding occurrences, number of occurrences, longest repeated substring; document retrieval, range minimum queries, least common ancestors (LCAs), finding longest palindrome, searching for pattern with mismatches
  Date: Monday, March 31, 2003
  Scribe: Michael Walfish
  [PostScript] [PDF]

• Lecture 11: Least common ancestors in constant time; suffix arrays, suffix links, constructing suffix trees in linear time (beyond alphabet sorting)
  Date: Wednesday, April 2, 2003
  Scribe: Loizos Michael and Christos Kapoutsis
  [PostScript] [PDF]

• Lecture 12: Succinct data structures, binary tries, rank, select, ordered rooted trees, balanced parentheses, related results
  Date: Monday, April 7, 2003
  Scribe: Wayland Ni and Gautam Jayaraman
  [PostScript] [PDF]

• Lecture 13: Compression, Huffman codes, arithmetic coding, higher-order entropy, Burrows-Wheeler transform, move-to-front transform, run-length encoding, theorems
  Date: Wednesday, April 9, 2003
  Scribe: Percy Liang and David Malan
  [PostScript] [PDF]

• Lecture 14: Ordered-file maintenance, analysis, order queries in lists, list labeling, external-memory model, cache-oblivious model
  Date: Monday, April 14, 2003
  Scribe: Kunal Agrawal and Vladimir Kiriansky
  [PostScript] [PDF]

• Lecture 15: Details and justification of cache-oblivious model, external-memory linked lists, cache-oblivious linked lists
  Date: Wednesday, April 16, 2003
  Scribe: Hans Robertson and Daniel Aguayo
  [PostScript] [PDF]

• Lecture 16: Divide-and-conquer, cache-oblivious median/select, cache-oblivious static search trees (binary search), cache-oblivious B-trees, external-memory sorting
  Date: Wednesday, April 23, 2003
  Scribe: Sonia Garg and Hana Kim
  [PostScript] [PDF]

• Lecture 17: External-memory sorting, cache-oblivious sorting, Funnelsort, cache-oblivious priority queues, Funnelheap
  Date: Monday, April 28, 2003
  Scribe: Jonathan Brunsman and Glenn Eguchi
  [PostScript] [PDF]

• Lecture 18: Tree-layout problem, minimizing maximum cost, minimizing expected cost, Split-and-Refine cache-oblivious layout
  Date: Wednesday, April 30, 2003
  Scribe: Rui Fan and Alan Leung
  [PostScript] [PDF]

• Lecture 19: Fault-tolerant data structures, model, stack, linked list
  Date: Monday, May 5, 2003
  Scribe: Ilya Baran, Deniss Cebikins, and Lev Teytelman
  [PostScript] [PDF]

• Project Presentations 1
  Date: Wednesday, May 7, 2003
  Scribe: Ray Jones and Mihai Patrascu
  [PostScript] [PDF]
  Presenters:
  • David Malan
  • Loizos Michael
  • Mihai Patrascu
  • Jonathan Brunsman and Sonia Garg
  • Ilya Baran, Denis Cebikins, and Lev Teytelman
  • Ray Jones

• Project Presentations 2
  Date: Monday, May 12, 2003
  Scribe: Ray Jones and Mihai Patrascu
  [PostScript] [PDF]
  Presenters:
  • William Kwong
  • Ben Leong
  • Rui Fan and Sayan Mitra
  • Jake Beal
  • Chris Collier
  • Sid Sen and Shantonu Sen
  • Alexandr Andoni and Cristian Cadar

• Project Presentations 3
  Date: Wednesday, May 14, 2003
  Scribe: Ray Jones and Mihai Patrascu
  [PostScript] [PDF]
  Presenters:
  • Percy Liang
  • Gautam Jayaraman
  • Hans Robertson
  • Glenn Eguchi and Hana Kim
  • Jeff Lindy
  • Lance Anderson and Wayland Ni
  • Vladimir Kiriansky