Advanced Data Structures

CS 598 JGE, Spring 2025

Main  ❖  Schedule  ❖  Projects

---

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)

• Michael Bender and Martín Farach-Colton. The LCA problem revisited. LATIN 2000.
• Stephane Durocher. A simple linear-space data structure for constant-time range minimum query. Munro Festschrift, 2013.
• Stephane Durocher and Robby Singh. A simple linear-space data structure for constant-time range minimum query. TCS 2019. Full version of previous paper, with experimental results.
• Johannes Fischer and Volker Heun. A new succinct representation of RMQ-information and im- provements in the enhanced suffix array. ESCAPE 2007. Describes a $O(1)$-time RMQ data structure that uses only $2n+o(n)$ bits, and proves a nearly matching $2n-o(n)$ lower bound.
• Matthew Skala. Array range queries. Munro Festschrift, 2013. Helpful survey about RMQ and related range searching problems in arrays.

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)

• Jeff's notes on amortized analysis
• Jon L. Bentley and James B. Saxe*. Decomposable searching problems I: Static-to-dynamic transformation. J. Algorithms 1(4):301–358, 1980.
• Mark H. Overmars*. The Design of Dynamic Data Structures. Lecture Notes Comput. Sci. 156. Springer-Verlag, 1983.
• Mark H. Overmars* and Jan van Leeuwen. Worst-case optimal insertion and deletion methods for decomposable searching problems. Inform. Process. Lett. 12(4):168–173, 1981.

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 trees.
• Robert Endre Tarjan. Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics 44. SIAM, 1983. See especially Chapter 4.

Feb 6

Cost models for dynamic binary search trees, Fredman's lower bound for HW0.2, Wilber's interleave lower bound, tango/multisplay trees intro
[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

Tango/multisplay tree details: preferred path decomposition, path splitting → tree splitting
Geometry of binary trees, arborally satisfied sets, GreedyFuture
[scribbles, video]

References (click to show/hide)

• Notes from Erik Demaine's advanced data structure class at MIT: scribbes 1, scribbles 2 scribe notes 1, scribe notes 2,
• Guy E. Blelloch and Magdalen Dobson. The geometry of tree-based sorting. Proc. 50th Int. Colloq. Automata Lang. Prog. (ICALP), 26:1–26:19, 2023. Leibniz Int. Proc. Informatics 261, Schloss Dagstuhl—Leibniz-Zentrum für Informatik.
• 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.
• Erik D. Demaine, Dion Harmon*, John Iacono, Daniel Kane*, and Mihai Pǎtraşcu. The geometry of binary search trees. Proc. 20th Ann. ACM-SIAM Symp. Discrete Algorithms, 496–505, 2009.
• Yaniv Sadeh and Haim Kaplan. Dynamic binary search trees: Improved lower bounds for the greedy-future algorithm. 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.

Feb 13

Euler-tour trees: subtrees → intervals, rotation updates, lazy updates
ST-trees: path decompositon (again), preferred-path parent pointers, accessing a node
[scribbles, video]

References (click to show/hide)

• Monika R. Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4):502–516, 1999. Euler-tour trees.
• Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3):362–391, 1983. ST-trees.
• Robert Endre Tarjan. Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics 44. SIAM, 1983. See especially Chapter 5.

Feb 18

ST-trees continued: heavy-path decomposition, access analysis, link/cut and path operations, evert, least common ancestors
[scribbles, video]

References (click to show/hide)

• Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3):362–391, 1983. ST-trees.
• Robert Endre Tarjan. Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics 44. SIAM, 1983. See especially Chapter 5.

Feb 20

Sketch of self-adjusting top trees; multiple-source shortest paths
[scribbles, video]

References (click to show/hide)

• Sergio Cabello, Erin W. Chambers, and Jeff Erickson. Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42(4):1542–1571, 2013. arXiv:1202.0314.
• Philip N. Klein. Multiple-source shortest paths in planar graphs. Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 146–155, 2005.
• Robert E. Tarjan and Renato F. Werneck. Self-adjusting top trees. Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 813–822, 2005.
• Robert E. Tarjan and Renato F. Werneck. Dynamic trees in practice. J. Exper. Algorithmics 14:5:1–5:21, 2009.

Feb 25 & 27

No lectures this week — Jeff is at SIGCSE

Mar 3

Paper chase assignment due

Mar 4

Dynamic connectivity
[scribbles, video]

References (click to show/hide)

• Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. Proc. 61st Ann. IEEE Symp. Found. Comput. Sci. (FOCS), 1158–1167, 2020. arXiv:1910.08025. $n^{o(1)}$ worst-case deterministic update time.
• David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification: A technique for speeding up dynamic graph algorithms. J. ACM 44(5):669–696, 1997. $O(\sqrt{n})$ worst-case deterministic update time.
• Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4):723–760, 2001. $O(\log^2 n)$ amortized deterministic update time.
• Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. Fully dynamic connectivity in $O(\log n (\log \log n)^2)$ amortized expected time. TheoretiCS 2(6), 2023.
• Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4):781–798, 1985. $O(\sqrt{m})$ amortized deterministic update time.
• Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. Proc. 24th ACM-SIAM Symp. Discrete Algorithms (SODA), 1131–1142, 2013. Monte Carlo algorithm with $O(\text{poly} \log n)$ worst-case update time against an oblivious adversary.

Mar 6

Lower bounds for dynamic connectivity
[scribbles, video]

References (click to show/hide)

• Michael L. Fredman. The complexity of maintaining an array and computing its partial sums. J. ACM 29(1):250–260, 1982. First use of the cell-probe model to prove dynamic data-structure lower bounds.
• Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. Proc. 21st Ann. ACM Symp. Theory Comput. (STOC), 345–354, 1989. $\Omega(\log n/\log\log n)$ lower bound for dynamic connectivity.
• Mihai Pătraşcu and Erik D. Demaine. Lower bounds for dynamic connectivity. (STOC), 546–553, 2004. $\Omega(\log n)$ lower bound for dynamic connectivity.
• Andrew Chi-Chih Yao. Should tables be sorted? J. ACM 28(3):615—628, 1981. Introduction of the cell-problem model. (Yao's answer is “Yes, if you can't use extra space. Otherwise no; use hashing instead.”)

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

---