- 2018 Spring/Summer (Jan - May)
Brief description: We will cover efficient algorithms for optimization and analysis of combinatorial objects, including graphs, matroids, polyhedra, and derived structures. This is intended to be a higher-level algorithms course. Topics to be covered include matchings, flows and cuts, matroids, matroid intersection, related polyhedra, and linear programming techniques.
References: primarily lecture notes from the course taught by Michel Goemans. The CLRS book is a reasonable initial reference. Other relevant books include "Combinatorial Optimization: Algorithms and Complexity" by Papadimitriou and Steiglitz, and "Combinatorial Optimization" by Cook et al.
Requirements: mathematical aptitude, including writing concise mathematical proofs. A previous course in discrete math, and a course in algorithms, are recommended but not required. You should be prepared to put in extra effort if you have not taken these courses.