Advanced Data Structures
Graduate data structures: persistence, geometry, dynamic optimality, cache-oblivious and integer structures, succinct structures and dynamic graphs.
Data structures sit underneath search engines, mail servers and network routers, and they are the building blocks of efficient algorithms. This graduate course covers the major results and current research directions in data structures, in recorded lectures with notes, at least half of it on work from the last decade: persistent and retroactive structures, geometric structures, dynamic optimality, memory hierarchy and cache-oblivious structures, integer structures such as fusion trees, strings, succinct structures and dynamic graphs.
What You Will Achieve
- Explain persistent, retroactive and geometric data structures and their trade-offs
- Analyze data structures under memory hierarchy and cache-oblivious models
- Use integer data structures such as fusion trees, and the lower bounds that limit them
- Describe succinct structures, string structures and dynamic graph connectivity
Program Overview
Time, Space and Geometry
Structures that remember the past or handle geometry.
- Persistent and retroactive data structures
- Geometric structures
- Dynamic optimality
Memory and Integer Models
How the model of computation shapes what is possible.
- Memory hierarchy models and cache-oblivious structures
- Dictionaries and integer models
- Fusion trees and integer lower bounds
- Sorting in linear time
Trees, Strings, Succinct Structures and Graphs
Specialized structures at the research frontier.
- Static trees and strings
- Succinct structures
- Dynamic graphs and the dynamic connectivity lower bound
- The history of memory models
Course Completion
Job Outlook
Advanced data structures are used in algorithm research, search and database engines, systems programming, computational geometry and high-performance software.
Good for: Learners drawn to theoretical computer science who want to see where data structures research stands.
Keep in mind: It is a research-level course: the final project is a theoretical contribution, an implementation study, a survey or Wikipedia articles, and the problem sets expect short typeset proofs.
Bottom line: A research-oriented tour of modern data structures, taught by Erik Demaine, with problem sets that have published solutions.
Frequently Asked Questions
How much of the course is recent research?
At least half of it covers research done in the decade before the course, alongside older results from the 1970s that remain important and have changed little.
What can the final project be?
A theoretical contribution or open problem, an implementation with experiments, a survey of a few papers, or a substantial improvement to Wikipedia articles on advanced data structures.
How are the problem sets written?
Each is one page typeset in LaTeX, meant to train the concise writing of research papers, and solutions are published for them.



There are no reviews yet.