Advanced Data Structures
For each lecture, I will provide links to scribbles ("boardwork"), videos, original papers, and other reading material, including my own typeset lecture notes for some topics, but definitely not all. Lecture topics in (parentheses) were briefly sketched or skipped entirely in the actual lecture, but may still appear in the lecture notes. A complete archive of lecture videos is available on a separate site.
I typically update this page only at the end of each week.
- Jan 21
-
Welcome and administrivia
Range-minimum queries: lookup tables, range trees, indirection, iterated logs
[scribbles,
video,
references below]
- Jan 23
-
Range-minimum queries: reduction to LCA via Cartesian trees, reduction to ±1RMQ via Euler tours, quadrimoscovian precomputation, $\sqrt{n}$-trees, bit packing
[scribbles,
video]
References (click to show/hide)
Open problem (click to show/hide)
Is there a data structure that maintains an n-element array using O(n) space, supports range-minimum queries in O(1) time, and supports updates (A[i] := x) in o(√n) time? There is an Ω(log n) lower bound (from sorting) and an O(√n) upper bound (due to Durocher).
- Jan 28
-
Static-to-dynamic transformations: Decomposable queries, logarithmic method, lazy rebuilding, anti-data structures for invertible queries
[scribbles,
video]
References (click to show/hide)
- Jan 30
-
Scapegoat trees: Global rebuilding, tombstones, local rebuilding, weight-balanced, height-balanced, ordered file maintenance, packed memory array (sketch)
[scribbles,
video]
References (click to show/hide)
-
Arne Andersson*.
Improving partial rebuilding by using simple balance criteria.
Proc. 1st WADS, 393–402, 1989. Lecture Notes Comput. Sci. 382, Springer-Verlag.
Scapegoat trees.
-
Arne Andersson.
General balanced trees.
J. Algorithms 30:1–28, 1999.
Journal version of previous paper.
[Preprint without publisher errors]
-
Michael A. Bender, Erik D. Demaine, and Martín Farach-Colton.
Cache-oblivious B-trees.
SIAM J. Comput. 35(2):341–358, 2005.
Simpler presentation of packed memory arrays.
-
Michael A. Bender, Martín Farach-Colton, and Miguel A. Mosteiro*.
Insertion sort is $O(n \log n)$.
Theory Comput. Sys. 39(3):391–397, 2006.
arXiv:cs/0407003.
Simplified packed memory arrays for random insertions.
-
Igal Galperin* and Ronald R. Rivest.
Scapegoat trees.
Proc. 4th SODA, 165–174, 1993.
-
Alon Itai, Alan G. Konheim, and Michael Rodeh.
A sparse table implementation of priority queues.
Proc. 8th ICALP
Jürg Nievergelt and Edward M. Reingold.
Binary search trees of bounded balance.
SIAM J. Comput.<./cite> 2(1):33–43, 1973. Weight-balanced ("BB[α]") trees.
-
Mark H. Overmars*.
The Design of Dynamic Data Structures.
Lecture Notes Comput. Sci. 156. Springer-Verlag, 1983.
Maintaining weight-balanced trees via local rebuilding.
- Feb 3
-
Add deadline
- Feb 4
-
Packed memory array details; splay trees
[scribbles,
video]
References (click to show/hide)
-
Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký,
William Kuszmaul, and Michael E. Saks.
Nearly optimal list labeling.
Proc. 65th Ann. IEEE Symp. Foundations Comput. Sci. (FOCS), 2253–2274, 2024.
arXiv:2405.00807.
Current best packed-memory array.
-
Michael A. Bender, Erik D. Demaine, and Martín Farach-Colton.
Cache-oblivious B-trees.
SIAM J. Comput. 35(2):341–358, 2005.
Simpler presentation of packed memory arrays.
-
Michael A. Bender, Martín Farach-Colton, and Miguel A. Mosteiro*.
Insertion sort is $O(n \log n)$.
Theory Comput. Sys. 39(3):391–397, 2006.
arXiv:cs/0407003.
Simplified packed memory arrays for random insertions.
-
Alon Itai, Alan G. Konheim, and Michael Rodeh.
A sparse table implementation of priority queues.
Proc. 8th ICALP
Daniel D. Sleator and Robert E. Tarjan.
Self-adjusting binary search trees.
J. ACM 32(3):652–686, 1985.
Splay tres.
- Feb 6
-
Cost models for dynamic binary search trees, Fredman's lower bound for HW0.2,
Wilber's interleave lower bound, tango/multisplay trees
[scribbles,
video]
References (click to show/hide)
-
Erik D. Demaine, Dion Harmon*, John Iacono, and Mihai Pătraşcu**.
Dynamic optimality—almost.
SIAM J. Comput. 37(1):240--251, 2007.
Tango trees.
-
Chengwen Chris Wang*, Jonathan Derryberry*, and Daniel~Dominic Sleator.
$O(\log \log n)$}-competitive dynamic binary search trees.
Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithms, 374--383, 2006.
Multisplay trees.
-
Michael L. Fredman.
Generalizing a theorem of {Wilber} on
rotations in binary search trees to encompass unordered binary trees.
Algorithmica 62(3):863--878, 2012.
-
John Iacono.
In pursuit of the dynamic
optimality conjecture.
Space-Efficient Data Structures, Streams, and Algorithms, 236--250, 2013.
Lecture Notes Comput. Sci. 8066, Springer-Verlag.
arXiv:1306.0207.
-
Robert E. Wilber*.
Lower bounds for accessing binary search trees with rotations.
SIAM J. Comput. 18(1):56--67, 1987.
- Feb 11
-
- Feb 13
-
- Feb 18
-
- Feb 20
-
- Feb 25
-
No lecture — Jeff is at SIGCSE
- Feb 27
-
No lecture — Jeff is at SIGCSE
- Mar 3
-
Paper chase assignment due
- Mar 4
-
- Mar 6
-
- Mar 11
-
- Mar 13
-
- Mar 14
-
Undergraduate drop deadline
- Mar 17-21
- Spring break — No lectures
- Mar 25
-
- Mar 27
-
- Mar 31
-
Project proposals due
- Apr 1
-
Overview of submitted project proposals
- Apr 3
-
- Apr 8
-
- Apr 10
-
- Apr 15
-
- Apr 17
-
- Apr 18
-
Graduate drop deadline
- Apr 22
-
- Apr 24
-
- Apr 29
-
- May 1
-
🔒 Final project presentations
- May 6
-
🔒 Final project presentations
- May 7
-
Project reports due
- May 8-9
- 🔒 Final project presentations (if necessary)
- May 10-16
- Jeff is at Dagstuhl