Lectures are MW 1–2:30 in 56-114.
| Scribe Notes | Prof. Notes | |||
|---|---|---|---|---|
| L1 | Mon., Feb. 12 | self-adjusting data structures : linked lists, Move To Front, Order By Next Request | Daniel Dumitran and Ray C. He [PDF] [TeX and Figures] | Erik's notes |
| L2 | Wed., Feb. 14 | self-adjusting data structures: splay trees, bounds, dynamic optimality conjecture | Christopher Moh and Aditya Rathnam [PDF] [TeX and Figures] | Erik's notes |
| L3 | Tue., Feb. 20 | self-adjusting data structures: Wilber lower bounds, key-independent optimality, O(lg lg n)-competitive Tango trees | Hui Tang [PDF] [TeX and Figures] | Erik's notes |
| L4 | Wed., Feb. 21 | dynamic graphs: dynamic trees (link-cut trees), Euler tour trees | Mashhood Ishaque [PDF] [TeX and Figures] | Erik's notes |
| L5 | Mon., Feb. 26 | dynamic graphs: overview, dynamic connectivity in O(lg2 n) | Katherine Lai [PDF] [TeX and Figures] | Erik's notes |
| L6 | Wed., Feb. 28 | dynamic graphs: Ω(lg n) lower bound for dynamic connectivity | Matthew Hofmann [PDF] [TeX and Figures] | Erik's notes |
| L7 | Mon., Mar. 5 | temporal data structures: persistence, retroactivity | Aston Motes and Kevin Wang [PDF] [TeX and Figures] | Erik's notes |
| L8 | Wed., Mar. 7 | strings: suffix tree, suffix array, document retrieval | Aston Motes and Kah Keng Tay [PDF] [TeX and Figures] | Erik's notes |
| L9 | Mon., Mar. 12 | strings: suffix tray, searching with errors and wild cards, level ancestor | Kuat Yessenov and Kevin Wang [PDF] [TeX and Figures] | Oren's notes |
| L10 | Wed., Mar. 14 | strings and geometry: approximate nearest neighbor via locality sensitive hashing. Guest lecture by Alex Andoni. | Alex Schwendner [PDF] [TeX and Figures] | Alex's slides |
| L11 | Mon., Mar. 19 | dictionaries: worst-case queries, via FKS and cuckoo hashing | Daw-Sen Hwang [PDF] [TeX and Figures] | Oren's notes |
| L12 | Wed., Mar. 21 | integers: models, y-fast trees, van Emde Boas | Tural Badirkhanli [PDF] [TeX and Figures] | Oren's notes |
| L13 | Mon., Apr. 2 | integers: fusion trees | Hooyoung Chung [PDF] [TeX] | Erik's notes |
| L14 | Wed., Apr. 4 | integers: predecessor lower bound via round elimination | Meshkat Farrokhzadi [PDF] [TeX] | Erik's notes |
| L15 | Mon., Apr. 9 | integers: tight time-space trade-off for predecessor. Guest lecture by Mihai Pătraşcu. | Ivaylo Riskov [PDF] [TeX and Figures] | Erik's notes |
| L16 | Wed., Apr. 11 | range queries and trees: static LCA, RMQ | Alison Cichowlas [PDF] [TeX] | Oren's notes |
| L17 | Wed., Apr. 18 | integers: sorting in linear time for w = O(lg2+ε n), priority queues | Eric Price [PDF] [TeX] | Erik's notes |
| L18 | Mon., Apr. 23 | integers: marked ancestor upper bound, decremental connectivity in trees | Pramook Khungurn, Boris Alexeev, Galen Pickard [PDF] [TeX and Figures] | Erik's notes |
| L19 | Wed., Apr. 25 | external memory / cache-oblivious: models, B-trees | Aditya Rathnam [PDF] [TeX] | Erik's notes |
| L20 | Mon., Apr. 30 | external memory / cache-oblivious: ordered-file maintenance, list labeling, order queries, priority queues | Robert Bryant [PDF] [TeX] | Erik's notes |
| L21 | Wed., May 2 | succinct data structures: rank, select, tries | Aaron Bernstein [PDF] [TeX and Figures] | Erik's notes |
| L22 | Mon., May 7 | succinct data structures: compact suffix arrays and trees | Marti Bolivar [PDF] [TeX] | Erik's notes |
| L23 | Wed., May 9 | student presentations: Christopher Moh, Daw-Sen Hwang, Ivaylo Riskov, Hooyoung Chung, Kuat Yessenov, Eric Price | Erik's notes | |
| L24 | Mon., May 14 | student presentations: Robert Bryant and Kevin Wang, Katherine Lai, Tural Badirkhanli, Galen Pickard, Anders Kaseorg, Hui Tang, Mashhood Ishaque | Erik's notes | |
| L25 | Wed., May 16 | student presentations: Aston Motes, Meshkat Farrokhzadi, Kah Keng Tay, Aaron Bernstein, Alex Schwendner, Matthew Hofmann and Aditya Rathnam, Boris Alexeev, Marti Bolivar | Erik's notes |
