• 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.
    Mon, Sep 12 Fibonacci heaps. MST. Persistent Data Structures.
    Wed, Sep 14 Persistent Data Structures. Splay Trees.
    Fri, Sep 16 Splay Trees.
    Mon, Sep 19 Buckets.
    Wed, Sep 21 Van Emde Boas Queues. Universal Hashing.
    Fri, Sep 23 Holiday
    Mon, Sep 26 Virtual. Perfect Hashing. Max Flow: Flow Decomposition. S-T Cuts.
    Wed, Sep 28 Max Flow: Max-Flow Min-Cut. Augmenting Path Algorithms.
    Schedule below subject to change.
    Fri, Sep 30 Blocking Flows. State-of-the-Art Max Flow Results.
    Mon, Oct 3 Min Cost Flows
    Wed, Oct 5 Min Cost Flow Algorithms
    Fri, Oct 7 Linear Programming: Introduction. Size of Solutions.
    Mon, Oct 10 Indigenous People’s Day - No class
    Wed, Oct 12 Linear Programming: Geometry. Structure of Optima. Duality Introduction.
    Fri, Oct 14 Linear Programming: Strong Duality.
    Mon, Oct 17 Linear Programming: Rules for Taking Duals. Duality Examples. Complementary Slackness.
    Wed, Oct 19 Linear Programming: Min-Cost Circulation Dual. Simplex Method.
    Fri, Oct 21 Linear Programming: Simplex Method. Ellipsoid Method.
    Mon, Oct 24 Linear Programming: Interior Point Method. Approximation Algorithms: Introduction.
    Wed, Oct 26 Approximation Algorithms: Greedy approaches. Scheduling. Approximation Schemes (PAS).
    Fri, Oct 28 Approximation Algorithms: Fully Polynomial Time Approximation Schemes (FPAS). Rounding. Enumeration.
    Mon, Oct 31 Approximation Algorithms: Relaxations. TSP. LP Relaxations.
    Wed, Nov 2 Approximation Algorithms: LP Relaxations. Facility Location. Approximation-Preserving Reductions.
    Fri, Nov 4 Approximation Algorithms: Randomized Rounding. Fixed Parameter Tractability.
    Mon, Nov 7 Treewidth. Computational Geometry: Range Trees. Sweep Algorithms.
    Wed, Nov 9 Computational Geometry: Voronoi Diagrams.
    Fri, Nov 11 Veteran’s Day
    Mon, Nov 14 Online Algorithms: Ski Rental. Finance.
    Wed, Nov 16 Online Algorithms: Load Balancing. Paging. Randomization.
    Fri, Nov 18 Online Algorithms: Paging. Randomization. K-Server Problem.
    Mon, Nov 21 Online Algorithms: K-Server Problem. External Memory Algorithms: Matrices. Linked Lists. Search Trees.
    Wed, Nov 23 External Memory Algorithms: Sorting. Buffer Trees. Cache Oblivious Algorithms.