Catalog

Advanced Data Structures

Electrical Engineering and Computer Science MIT CC BY-NC-SA 4.0 22 lectures

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. This course covers major results and current directions of research in data structure. Acknowledgments --------------- Thanks to videographers Martin Demaine and Justin Zhang.

Syllabus

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

Course materials