Lecturer
See Frank’s website for a merged and up-to-date version of the notes.
Lecture Notes
Problem Sets
- ProblemSet1.pdf
- ProblemSet1Solutions.pdf
- ProblemSet2.pdf
- ProblemSet2Solutions.pdf
- ProblemSet3.pdf
- ProblemSet3Solutions.pdf
- ProblemSet4.pdf
- ProblemSet4Solutions.pdf
- ProblemSet5.pdf
- ProblemSet5Solutions.pdf
- ProblemSet6.pdf
- ProblemSet6Solutions.pdf
- ProblemSet7.pdf
- ProblemSet7Solutions.pdf
- ProblemSet8.pdf
- ProblemSet8Solutions.pdf
- ProblemSet9.pdf
- ProblemSet9Solutions.pdf
- ProblemSet10.pdf
- ProblemSet10Solutions.pdf
- ProblemSet11.pdf
- ProblemSet11Solutions.pdf
- ProblemSet12.pdf
- ProblemSet12Solutions.pdf
Texts
Online lecture notes:
- By Alexander Schrijver
- By Jeff Erickson (lecture 18-26, 29,30)
- By Michel Goemans (see notes at the bottom)
- Matroids You Have Known (friendly introduction to matroids)
- By Serge Plotkin (good for approximation algos)
- By Luca Trevisan (similar to Plotkin, more detail)
- By Alexander Souza (also good for approximation algos)
- TSP stuff
Books:
- Korte, Vygen – Combinatorial Optimization: Theory and Algorithms
- Schrijver – Combinatorial Optimization: Polyhedra and Efficiency
- Cook, Cunningham, Pulleyblank, Schrijver – Combinatorial Optimization
- Matoušek, Gärtner – Understanding and Using Linear Programming
- Vazirani – Approximation Algorithms
Schedule
- Lectures: Thursdays, 15-17pm, MA A3 30
- Exercises: Tuesdays, 17-19pm, MA A3 31
Exam
- The exam is on Tuesday, January 22nd, from 8:15am to 11:00am, in CM1104.
- Below is a practice exam. I will post solutions about a week before the exam.
- Email me if you have any questions.