Lectures and Preparation
We will cover the following topics in this course. The provided number of weeks is approximate.
- Greedy Algorithms (2 weeks)
- Dynamic Programming (2-3 weeks)
- Network Flow (2 weeks)
- Linear Programming (1-2 weeks)
- NP-Completeness (3 weeks)
The following table contains the specific sections of the textbook and the notes for each week. The notes will be posted at the end of the week, summarizing the material covered in the lectures. Readings are from the textbook.
These lecture notes are based on the notes by Francois pitt and the notes by Allan Borodin. I would like to thank them for their generosity.
| Week | Topics | Lecture notes | Tutorial notes |
|---|---|---|---|
| 1 | Background (Chapters 0, 2, 3, 4.2) and Greedy algorithms (Chapter 5.1) | Lecture 1 | |
| 2 | Readings: Chapters 5.1, 4.4 | Lecture 2 | Tutorial 1 |
| 3 | Readings: Chapters 5.2, 6.1 | Lecture 3 | Tutorial 2 |
| 4 | Readings: Chapters 6.4, 6.5, 6.6 | Lecture 4 | Tutorial 3 |
| 5 | Readings: Chapter 7.2 | Lecture 5 | Tutorial 4 |
| 6 | Readings: Chapter 7.3 | Lecture 6 | Tutorial 5 |
| 7 | Reading week | No Lecture! | No Tutorial! |
| 8 | Readings: Chapters 7.1, |
Lecture 7 | Tutorial 6 |
| 9 | Lecture 8 | Midterm solutions | |
| 10 | Readings: Chapter 8.2 | Lecture 9 | Tutorial 8 -- updated |
| 11 | Readings: Chapter 8.3 (and 8.1 for problem definitions) | Lecture 10 | Tutorial 9 |
| 12 | Lecture 11 | Tutorial 10 | |
| 13 | Lecture 12 | A3 solutions |