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

    For notes and videos related to each topic, see the course materials.

    Date Topic
    Wed, Sep 7 Course introduction. Fibonacci heaps.
    Fri, Sep 9 Fibonacci heaps. MST.
    Mon, Sep 12 Persistent Data Structures.
    Wed, Sep 14 Splay Trees.
    Fri, Sep 16 Splay Trees. Buckets.
    Mon, Sep 19 Van Emde Boas Queues. Universal Hashing.
    Wed, Sep 21 Universal Hashing. Perfect Hashing. Max Flow.
    Fri, Sep 23 Holiday
    Mon, Sep 26 Max Flow: Max Flow Min Cut. Augmenting Path Algorithms.
    Virtual: Pt 1, Pt 2 until 52 minutes
    Wed, Sep 28 Max Flow: Augmenting Path and Strongly Poly Algorithms.
    Fri, Sep 30 Max Flow: Strongly Poly Algorithms and Blocking Flows.
    Mon, Oct 3 Blocking Flows and Min Cost Flow
    Wed, Oct 5 Min Cost Flow Algorithms.
    Virtual: Pt 1, Pt 2 until 30 minutes
    Fri, Oct 7 Min Cost Flow. Linear Programming: Introduction.
    Mon, Oct 10 Indigenous People’s Day - No class
    Wed, Oct 12 Linear Programming: Size of Solutions. Geometry. Structure of Optima.
    Fri, Oct 14 Linear Programming: Structure of Optima. Weak Duality. Strong Duality Physics Proof.
    Mon, Oct 17 Linear Programming: Strong Duality Formal Proof. Rules for Taking Duals. Shortest Paths Dual.
    Virtual: Pt 1, Pt 2 until 42 minutes
    Wed, Oct 19 Linear Programming: Max Flow Dual. Complementary Slackness. Min-Cost Circulation Dual.
    Fri, Oct 21 No class
    Mon, Oct 24 Linear Programming Algorithms: Simplex Method.
    Wed, Oct 26 Linear Programming Algorithms: Simplex and Duality. Ellipsoid Method.
    Fri, Oct 28 Approximation Algorithms: Introduction. Greedy approaches.
    Mon, Oct 31 Linear Programming Revisited: Interior Point Method. Approximation Algorithms: More Greedy Examples. Scheduling.
    Wed, Nov 2 Approximation Algorithms: Approximation Schemes. Rounding. Enumeration.
    Fri, Nov 4 Approximation Algorithms: Enumeration. Relaxations: MST, TSP.
    Mon, Nov 7 Approximation Algorithms: Scheduling Relaxation. LP Relaxations. Facility Location.
    Wed, Nov 9 Approximation Algorithms: Facility Location. MAX-SAT. Randomized Rounding.
    Fri, Nov 11 Veteran’s Day
    Mon, Nov 14 Computational Geometry: Range Trees. Sweep Algorithms. Voronoi Diagrams.
    Wed, Nov 16 Vornoi Diagrams Continued. Online Algorithms Introduction
    Fri, Nov 18 Online Algorithms: Ski Rental. Finance. Load Balancing. Paging.
    Mon, Nov 21 Online Algorithms: Randomization. K-Server Problem.
    Wed, Nov 23 Online Algorithms: Lower Bounds. External Memory Algorithms: Matrices. Linked Lists.
    Schedule below subject to change.
    Mon, Nov 28 External Memory Algorithms: Search Trees. Sorting. Buffer Trees. Cache Oblivious Algorithms.
    Bonus Fixed Parameter Tractability. Treewidth.