Slides

If you wish to view the MS journal files, you can download the following viewer. Alternatively, you can view the PDF files.

1. Jan. 21 What is linear programming? PDF version
2. Jan. 24 Introduction to network flow. PDF version
3. Review of flow augmenting algorithms, matching and vertex cover in bipartite graphs, introduction to push-relabel. PDF version
4. Push-Relabel algorithm. PDF version
5. Implementation of push-relabel in $O(n^3)$ & flow with lower bounds. PDF version
6. Global min-cut algorithms in undirected graphs. PDF version
7. Min cost flow: definitions, Klein's algorithm, Scaling algorithm. PDF version
8. Minimum cycle mean algorithm. PDF version
9. Maximum matching algorithm in general graphs. PDF version
10. Edge coloring (Vizing) . PDF version
11. Geometry of linear programming. PDF version
12. LP: extreme points & Fourier-Motzkin Elimination. PDF version
13. LP: Farkas Lemma & Strong Duality. PDF version
14. Duality and complementary slackness. PDF version
15. Simplex: rational. PDF version
16. Primal-Dual algorithm. PDF version