Lectures

01. Basic concepts in optimization
02. Basic concepts in Graph algorithms
03. Shortest paths algorithms
04. Negative length cycles
05. Minimum ratio cycles
06. Image segmentation (shortest paths and ratio cycles).
07. Edit distance and sequence alignment
08. Sequence alignment via shortest paths
09. Matroids (part 1)
10. Matroids (part 2)
11. Greedy algorithm
12. Matroid intersection + metric TSP approximation
13. Linear programming concepts
14. Maximum flow LP
15. LP geometry
16. Simplex
17. Vertex-cover approximation (LP rounding)
18. MAX 2-sat approximation (LP rounding)
19. Set cover approximation (greedy)
20. Knapsack (DP)
21. Knapsack Approximation scheme
22. Min-cuts and Random contraction
23. Random contraction implementation
24. Max-Cut approximation via local search
25. Max-Cut approximation via vector programming rounding
26. Semidefinite programming
27. Max cardinality bipartite Matching (augmenting paths)
28. Min weight perfect matching (LP)
29. Branch and Bound ideas
30. Branch and Bound for Integer Programs