| 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. |