Combinatorial optimization 2023 spring
Location:
Each Friday at 12:15 E302 IB134
On every second Tuesday at 17:00: IB138
Consulting hours: Friday 10:00-11:30 IE217.3
Requirements:
There will be two midterm tests during the semester. There will be two occasions at the end of the semester where you can retake a midterm. You have to receive at least 40% of the points (which means 20 points per test) at each test to complete the course.
Helpful materials:
Book: Cormen, Leiserson, Rivest and Stein: Intorudction to Algorithms
Alexander Schrijver's lecture notes on combinatorial optimization.Midterms:
- 1st Midterm: 19th of April, 18:00 Location: IB025 (Building I)
- 1st Midterm retake:: 3rd of May, 18:00 location: IB025 (Building I)
- 2nd Midterm: 26th of May, 12:00 Location: E302 (Building E)
- 2nd Midterm retake (where you can retake only the 2nd midterm): 5th of June, 8:00 Location: IB134
Timetable:
| Week | Time | Info | Slides/Problem sheet | Additional Material |
|---|---|---|---|---|
| 1. | 3rd of March | Introduction to algorithms, Big O notation | ||
| 2. | 7th of February | Practice session | 1st practice sheet | |
| 10th of March | Magnitude of functions, Introduction to graphs | |||
| 3. | 17th of March | Minimum weight spanning tree, TSP | ||
| 4. | 21th of March | |||
| 24th of March | Practice session | 2nd practice sheet | ||
| 5. | 31st of March | Shortest paths | ||
| 6. | 4th of April | Lecture | Decision problems, Matching theory | |
| 7th of April | Holiday, No lecture | |||
| 7. | 14th of April | Practice session | 3rd practice sheet | |
| 8. | 18th of April | Lecture | NP class, Karp-reduction | |
| 19th of April | 1st midterm | |||
| 21st of April | NP-complete problems, Approximation algorithms | |||
| 9. | 28th of April | 4th practice sheet | ||
| 10. | 2nd of May | Linear programming | ||
| 3rd of May | First midterm retake | |||
| 5th of May | No lecture | |||
| 11. | 12th of May | 5th practice sheet | ||
| 12. | 16th of May | Duality theorem, IP | ||
| 19th of May | Practice session | 6th practice sheet | ||
| 13. | 26th of May | 2nd Midterm in Lecture time at E302 | ||
| 14. | 30th of May | Integer programming, TU matrices | ||
| 2nd of June | Practice session | 7th practice sheet |