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)
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)
Feb 3
Add deadline
Feb 4
Packed memory array details; splay trees
[scribbles, video]
References (click to show/hide)
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)
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