These are rough, personal lecture notes handwritten by Erik Demaine
used during lecture. Their primary purpose is for reading/review by students
before the scribe notes (which are more complete) become available. See the
scribe notes page.
Accessibility
- Lecture 1: Fixed-universe successor problem, van Emde Boas -- pages 1, 2, 3, 4
- Lecture 2: More van Emde Boas, reducing space, dynamic perfect hashing, y-fast trees,
transdichotomous RAM -- pages 1, 2, 3, 4, 5
- Lecture 3: RAMBO model, constant-time RAMBO van Emde Boas, finding least-significant 1-bit, decision-tree model and lg lower bound -- pages 1, 2, 3, 4
- Lecture 4: Fusion trees -- pages 1, 2, 3, 4, 5
- Lecture 5: More fusion trees; self-organizing data structures, move-to-front, static optimality -- pages 1, 2, 3
- Lecture 6: Dynamic optimality of move-to-front, omniscient Order-by-Next-Request beats online algorithms -- pages 1, 2, 3
- Lecture 7: Entropy bound of Order-by-Next-Request, optimal binary search trees, self-adjusting trees, splay trees, bounds -- pages 1, 2, 3, 4
- Lecture 8: Unified property, working-set structure, unified structure -- pages 1, 2, 3, 4, 5
- Lecture 9: More unified structure, key-independent optimality, Wilber's lower bound, Munro's offline binary search tree -- pages 1, 2, 3, 4
- 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 -- pages 1, 2, 3
- Lecture 11: Least common ancestors in constant time; suffix arrays, suffix links, constructing suffix trees in linear time (beyond alphabet sorting) -- pages 1, 2, 3, 4, 5
- Lecture 12: Succinct data structures, binary tries, rank, select, ordered rooted trees, balanced parentheses, related results -- pages 1, 2, 3, 4
- Lecture 13: Compression, Huffman codes, arithmetic coding, higher-order entropy, Burrows-Wheeler transform, move-to-front transform, run-length encoding, theorems -- pages 1, 2, 3, 4, 5
- Lecture 14: Ordered-file maintenance, analysis, order queries in lists, list labeling, external-memory model, cache-oblivious model -- pages 1, 2, 3, 4
- Lecture 15: Details and justification of cache-oblivious model, external-memory linked lists, cache-oblivious linked lists -- pages 1, 2, 3
- Lecture 16: Divide-and-conquer, cache-oblivious median/select, cache-oblivious static search trees (binary search), cache-oblivious B-trees, external-memory sorting -- pages 1, 2, 3, 4
- Lecture 17: External-memory sorting, cache-oblivious sorting, Funnelsort, cache-oblivious priority queues, Funnelheap -- pages 1, 2, 3, 4, 5
- Lecture 18: Tree-layout problem, minimizing maximum cost, minimizing expected cost, Split-and-Refine cache-oblivious layout -- pages 1, 2, 3, 4
- Lecture 19: Fault-tolerant data structures, model, stack, linked list -- pages 1, 2, 3, 4