Fractional cascading in 3D orthogonal range searching in O(log n) time. Moving data, e.g., where 2D points move at known velocity and acceleration: kinetic predecessor and kinetic priority queues.

1. Persistent Data Structures
2. Retroactive Data Structures
3. Geometric Structures I
4. Geometric Structures II
5. Dynamic Optimality I
6. Dynamic Optimality II
7. Memory Hierarchy Models
8. Cache-Oblivious Structures I
9. Cache-Oblivious Structures II
10. Dictionaries
11. Integer Models
12. Fusion Trees
13. Integer Lower Bounds
14. Sorting in Linear Time
15. Static Trees
16. Strings
17. Succinct Structures I
18. Succinct Structures II
19. Dynamic Graphs I
20. Dynamic Graphs II
21. Dynamic Connectivity Lower Bound
22. History of Memory Models

Data structures play a central role in modern computer science. You interact with data structures even more often than with algorithms (think Google, your mail server, and even your network routers). In addition, data structures are essential building blocks in obtaining efficient algorithms.

For a list of major results and current directions of research in data structures covered by this course, please see the syllabus.