Lectures

01. Basic concepts
02. Dijkstra's shortest paths [1,2,3,4]
03. Bellman-Ford shortest paths, negative cycle detection, [1,2,3,4]
04. Applications
05. Interactive image segmentation and mean-length cycles [1]
06. Mean-length cycles [1]
07. Min-cuts, Random contraction algorithm [4,5]
08. Random contraction, weighted min-cut [4,5]
09. Spectral clustering
10. Spectral clustering
11. Max-flow, st-cuts, Ford-Fulkerson algorithm [1,2,4]
12. Ford-Fulkerson algorithm [1,2,4]
13. Network routing problems, Max-cardinality matching
14. Image restoration
15. Linear programming applications [2]
16. Linear programming concepts [2]
17. Simplex algorithm [2]
18. Simplex algorithm [2]
19. Linear programming duality
20. Integer solutions, totally unimodular matrices [1]
21. Totally unimodular matrices, incidence matrices [1]
22. LP applications (multicommodity flow, robust regression)
23. Max-cut via local-search [4]
24. Set cover, greedy approximation algorithm
25. Set cover, LP relaxation and rounding
26. Knapsack, dynamic programming [4]
27. Knapsack approximation algorithm [4]
28. TSP, MST approximation
29. TSP, Christofides algorithm, applications
30. Applications in Computer Vision

References
[1] Combinatorial Optimization. Schrijver. Springer.
[2] Introduction to Algorithms. Cormen, Leiserson, Rivest, Stein. MIT Press.
[3] The Design and Analysis of Computer Algorithms. Aho, Hopcroft, Ullman. Addison-Wesley.
[4] Algorithm Design. Kleinberg, Tardos. Addison-Wesley.
[5] Randomized Algorithms. Motwani and Raghavan.