Lectures are TR 11–12:30 in
36-153 26-100
The calendar of lectures is also available in iCalendar format.
| Scribe Notes | Prof. Notes | ||||
|---|---|---|---|---|---|
| L1 | Tue., Feb. 2 | dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm | Kevin Kelley [PDF] [TeX] | Erik's notes | |
| L2 | Thu., Feb. 4 | dynamic optimality: independent rectangle, Wilber, and Signed Greedy lower bounds; key-independent optimality; O(lg lg n)-competitive Tango trees | Prasant Gopal [PDF] [TeX and Figures] | Erik's notes | |
| L3 | Tue., Feb. 9 | geometric data structures: orthogonal range queries, range trees, fractional cascading | Jacob Steinhardt and Greg Brockman [PDF] [TeX and Figures] | André's notes | |
| L4 | Thu., Feb. 11 | geometric data structures: stabbing queries, interval trees, segment trees, priority search trees, windowing | Peter Caday [PDF] [TeX] and Cai GoGwilt [PDF] [TeX and Figures] | André's notes | |
| L5 | Thu., Feb. 18 | geometric data structures: kinetic data structures and ray shooting (1) | David Stein and Jacob Steinhardt [PDF] [TeX and Figures] | Erik's notes André's notes | |
| L6 | Tue., Feb. 23 | geometric data structures: ray shooting (2), partition trees | Reid Kleckner and Skye Wanderman-Milne [PDF] [TeX] | André's notes | |
| L7 | Thu., Feb. 25 | strings: suffix tree, suffix array, document retrieval | Mark Chen [PDF] [TeX and Figures] | André's notes | |
| L8 | Tue., Mar. 2 | strings: level ancestor, static LCA (part 1) | Andrew Winslow [PDF] [TeX and Figures] | André's notes incl. LCA part 2 | |
| L9 | Thu., Mar. 4 | strings: static LCA (part 2) integers: van Emde Boas, y-fast trees |
Paul Christiano [PDF] [TeX] | André's notes | |
| L10 | Tue., Mar. 9 | integers: fusion trees | Nicholas Zehender [PDF] [TeX] | Erik's notes | |
| L11 | Thu., Mar. 11 | integers: predecessor lower bound via round elimination | Jingjing Liu [PDF] [TeX] | Erik's notes | |
| L12 | Tue., Mar. 16 | integers: sorting in linear time for w = O(lg2+ε n), priority queues | Haitao Mao [PDF] [TeX] | Erik's notes | |
| L13 | Thu., Mar. 18 | integers: tree decompositions, marked ancestor upper bound, decremental connectivity in trees | David Charlton [PDF] [TeX] | Erik's notes | |
| L14 | Tue., Mar. 30 | dictionaries: FKS and cuckoo hashing | David Wilson [PDF] [TeX] [Fig], Rishi Gupta [PDF] [TeX] | André's notes | |
| L15 | Thu., Apr. 1 | dictionaries: deterministic dictionaries | OLD: Catherine Miller [PDF] [TeX and Figures] | André's notes | |
| L16 | Tue., Apr. 6 | dynamic graphs: dynamic trees (link-cut trees) | OLD: Mashhood Ishaque [PDF] [TeX and Figures] | André's notes | |
| L17 | Thu., Apr. 8 | dynamic graphs: overview, Euler tour trees, dynamic connectivity in O(lg2 n) | TB Schardl [PDF] [TeX] [Figures] | André's notes | |
| L18 | Tue., Apr. 13 | dynamic graphs: Ω(lg n) lower bound for dynamic connectivity | Morteza Zadimoghaddam [PDF] [TeX] | Erik's notes | |
| L19 | Thu., Apr. 15 | temporal data structures: persistence, retroactivity | Ye Wang [PDF] [TeX] | Erik's notes | |
| L20 | Thu., Apr. 22 | external memory / cache-oblivious: models, B-trees | Eric Liu [PDF] [TeX] | Erik's notes | |
| L21 | Tue., Apr. 27 | external memory / cache-oblivious: ordered-file maintenance, list labeling, order queries, priority queues | Tom Morgan [PDF] [TeX] [figures] | Erik's notes | |
| L22 | Thu., Apr. 29 | succinct data structures: rank, select, tries | Morteza Zadimoghaddam [PDF] [TeX] | Erik's notes | |
| L23 | Tue., May 4 | succinct data structures: compact suffix arrays and trees | Sarah Eisenstat [PDF] [TeX] | Erik's notes | |
| L24 | Thu., May 6 | student presentations: Peter Caday & Rishi Gupta, Cai GoGwilt & Matthew Huang, Reid Kleckner, Jacob Steinhardt & Ye Wang, Andrew Winslow | Erik's notes | ||
| L25 | Tue., May 11 | student presentations: Mark Chen & Haitao Mao, Eric Liu & Tom Morgan, Jingjing Liu, Kevin Kelley & TB Schardl, Nicholas Zehender | Erik's notes | ||
| L25 | Thu., May 13 | student presentations: David Charlton, Paul Christiano and Shaunak Kishore, Sarah Eisenstat, David Stein, David Wilson | Erik's notes |
