|
Course Outline
Topics covered in the class
Jan. 7: Introduction and review of linear optimization.
Jan. 9: Combinatorial Optimization problems.
Jan. 14: Introduction of graphs and diagraphs; Shortest Path problem and Bellman's equation.
Jan. 16: Bellman's equation and Dijkstras's algorithm.
Jan 21: Rationale of Dijkstras's algorithms, complexity, more examples.
Jan 23: Lawler's version, complexity, Bellman-Ford algorithm.
Jan. 28: Rationale of Bellman-Ford algorithm
Jan. 30: Floyd-Warshall's algorithm for all pairs of nodes
Feb. 4: Minimum spanning trees and Kruskal's algorithms; rationale.
Feb. 6: Rationale of Prim's algorithms, Networks
Feb. 11: Network flow problem and FAP
Feb. 13: Minimum cut and maximal flow
Feb. 16-20: reading week.
Feb. 25: review and proofs of theorems, Ford-Fulkerson algorithm.
Feb. 27: More examples of Ford-Fulkerson algorithm.
Mar. 4: Cardinality matching problem.
Mar. 6: Midterm.
Mar. 11: More examples of Cardinality matching problems; complexity of Ford-Fulkerson algorithm preflows
Mar. 13: Preflows and distance labelling.
Mar. 18: The preflow push algorithm (Goldberg's algorithm)
Mar. 20: A complete example.
Mar. 25: Analysis of preflow push algorithm
|