6.851: Advanced Data Structures (Spring'07)

Prof. Erik Demaine     TA: Oren Weimann

[Home] [Lectures] [Assignments] [Project]

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