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 |