General Information: the course will mostly draw material from the following two books.

Combinatorial Optimization, by Cook, Cunningham, Pulleyblank and Schrijver.
Network flows: theory, algorithms, and applications, by Ahuja, Magnanti, and Orlin.

September 28. We talked about the preflow-push algorithm and Edmonds-Karp algorithm for maximum flow.
October 5. We presented an algorithm for maximum density subgraph problem. We then presented Berge's theorem, Konig's theorem and Egervary's theorem. The first homework exericse is here. The solution is here.
October 12. We talked about Karger's min-cut algorithm and Gomory-Hu trees.
October 19. We presented Edmonds' blossom algorithm.
October 25. It is about the matroids. The second homework exericse is here. The solution is here.
November 9. We talk about multi-commodity flow and k-coverage problems.