Topics in Optimization (ENGN 2912P)

Home   Assignments   Lectures  
Lecture: MWF 11am-11:50am in Barus & Holley 155

Pedro Felzenszwalb
Email: pff (at)
Office: Barus & Holley 355

Course description
This course will cover various topics in discrete and continuous optimization. Topics include graph algorithms, dynamic programming, linear programming, convex optimization and coarse-to-fine methods.

Combinatorial Optimization. Schrijver. Springer.
Introduction to Algorithms. Cormen, Leiserson, Rivest, Stein. MIT Press.
The Design and Analysis of Computer Algorithms. Aho, Hopcroft, Ullman. Addison-Wesley.
Algorithm Design. Kleinberg, Tardos. Addison-Wesley.

Preliminary list of topics for 2014

Shortest paths
- Dijkstra, Bellman-Ford, Floyd-Warshall
- Min-plus matrix multiplication
- Minimum-ratio paths
- String edit and time warping

- Spanning trees and other applications
- Greedy algorithm
- Matroid intersection

- Max-flow / Min-cut
- Min-cost circulation
- Bipartite matching

Linear programming
- Simplex
- Duality

Dynamic programming
- Sequence labeling
- Graph labeling
- Piecewise quadratic fitting

Approximation algorithms
- Min-cover (greedy)
- Max-cut (local search)
- Packing (rounding + DP)
- LP relaxation

Other topics
- Branch-and-bound
- Heuristic search
- Local search
- Convex optimization