6.851: Advanced Data Structures (Spring'10)

Prof. Erik Demaine     Dr. André Schulz     TA: Aleksandar Zlateski

[Home] [Lectures] [Assignments] [Project] [Problem Session]

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