• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Course Materials

    We’ve done our best to synchronize a breadth of materials developed over this course’s history for your reference. But be aware that some of the materials here — particularly the scribe notes and 2013 lectures — do not necessarily reflect exactly what has or will happen in this year’s class. Be sure to check this year’s course calendar for the most up-to-date syllabus.

    Unit Topic Notes Scribe 2013 2020 2021 2022
    Introduction 1 1
     
    Data Structures Fibonacci Heaps 1 1 1, 2
    Persistent 1 1 1, 2
    Splay Trees 1 1 1, 2 1, 2, 3
    Buckets 1 1, 2 1, 2 1
    ↳VeB Queues ^ 1 1 1
    Hashing 1 1 1, 2 1, 2
    ↳Perfect ^ ^ 1 1 1
     
    Flow Maximum Flow 1 1 1 1, 2 1, 2
    ↳Algorithms 1 ^ 1 1, 2 1
    ↳Strongly Poly 1 1 1 1, 2
    ↳Blocking 1 1 1, 2 1 1
    Min Cost Flow 1 1 1 1
    ↳Algorithms ^ ^ 1, 2 1, 2 1
     
    Linear Programming Introduction 1 1 1, 2 1, 2
    Geometry & Optima ^ 1 1 1, 2 1
    Duality 1 1 1 1, 2 1,2,3
    ↳Practice ^ 1 1 1, 2 1, 2
    Algorithms 1 1 1, 2 1, 2 1,2,3
     
    Approximation Greedy 1 1 1 1, 2 1, 2
    Schemes ^ ^ 1, 2 1, 2 1, 2
    Relaxations ^ 1, 2 1, 2 1
    ↳LP ^ 1 1, 2 1,2,3
     
    Fixed Parameter Tractability Introduction 1 1 1 1
    Treewidth ^ ^ 1 1, 2
     
    Comp. Geometry Range Search 1 1 1
    Sweep ^ 1 1 1
    Voronoi ^ 1 1 1, 2
     
    Online Introduction 1 1 1 1, 2
    Paging ^ 1 1 1, 2 1
    ↳Randomized ^ ^ 1 1, 2 1, 2
    ↳K-Server ^ ^ 1, 2 1, 2
     
    External Memory 1 1 1, 2 1, 2
     
    Parallel 1 1, 2