This course implements an algorithmic branch of discrete math. It teaches algorithmic graph theory and linear programming.
Overview
Week 1 (Independence Systems): Independence Systems, Rank, Matroids, Greedy Min/Max/Dual, Edmonds-Rado-Thm, Rank Quotient
Week 2 (Branchings): Arborescences, Branchings, Edmonds Alg.
Week 3 (Complexity): Encoding Length, Run Time of Algorithms, Classes P, NP, co-NP, NP-Completness, SAT, Reductions
Week 4 (Shortest Paths): Dijkstra Alg., [A* Alg.], Bellman Recursion, Floyd-Warshall Alg.
Week 5 (Minimum Mean Cycles): Karp Alg.
Week 6 (Maximum Flows): Menger, Augmenting Paths, Edmonds-Karp Alg. Max Flow Min Cut Thm, [Blocking Flows, Dinics Alg.]
Week 7 (Minimum Cost Flows): Generalized Max Flow Min Cut Thm, Equiv. to Transportation Problem, Residual Graph, Min. Mean Cycle Cancelling Alg., Sucessive Shortest Path Alg.
Week 8 (Matchings): Alternating and Augmenting Paths, Hopcroft-Karp Alg. (for the Cardinality Case)
Week 9 (Polyhedra): Polyhedra, Valid Inequalities, Faces and Facets, Vertices and Extreme Rays, H and V Representation, Caratheodory Thm
Week 10 (Fesibility): Fourier-Motzkin Elimination, Alternative Thms, Farkas Lemma, Redundancy, Degeneracy, Transformations of Polyhedra
Week 11 (Bases): Equality Set, Dimension, Basis, Vertices and Bases
Week 12 (Linear Programs): Primal/Dual LP, Week Duality, Standard Form, Optimality Criterion, Strong Duality, Complementary Slackness
Week 13 (Simplex I): Tableau, Revised Simplex Method, Degenerary, Finiteness, Worst-Case Behavior
Week 14 (Simplex II): Dual Simplex, Sensitivity Analysis
Week 15 (Interior Point Algorithms and Ellipsoid Method, Overview only): Primal-Dual Formulation, Barrier Problem, KKT-Systen, Central Path, Path Following Methods, Run Time, Ellipsoids, Volume, Löwner-John-Ellipsoid, Ellpsoid Method, Run Time
Week 16 (Reserve Time, Wrap up, and Exam)