A self-adjusting binary tree, drawn by Jorge Stolfi
|
A self-adjusting binary tree, drawn by Jorge Stolfi |
This course covers a variety of modern techniques for designing and analyzing data structures. The exact topics will depend on student (and instructor) interest—There is far too much material to cover in a single semester!—but I will try to touch on a few broad themes:Students are strongly encouraged to suggest specific topics for future lectures or discussion.
- Fun with pointers: Pointer-based data structures that are randomized, self-adjusting, dynamic, multilevel, lazy, persistent, kinetic, retroactive, succinct, competitive, fault-tolerant, and/or cache-oblivious. Probably not all at once, but hey, you never know.
- Fun with bits: Data structures that exploit word-level parallelism to ignore information-theoretic lower bounds. Sorting in O(n sqrt{log log n}) time and other "impossible" tricks.
- Fun with sets: Lower bounds for data structure problems, mostly in the cell-probe, pointer machine, and semigroup arithmetic models.
See also these web pages for other advanced data structure courses:
- Lars Arge and Gerth Brodal's Advanced Data Structures course at Aarhus
- Erik Demaine's Advanced Data Structures course at MIT
- Faith Fich's Dynamic Data Structures course at Toronto
- Haim Kaplan's Advanced Topics in Data Structures course at Tel Aviv
- Pat Morin's Advanced Data Structures course at Carleton
- Rajeev Motwani's Advanced Data Structures and Algorithms course at Stanford
- Danny Sleator's Advanced Data Structures course at CMU