| [Announcements] | [General Information] | [Additional Material] | [Schedule] |
In this course we cover basic algorithmic techniques for dealing with problem that (probably) cannot be solved in polynomial time. We cover the basic toolbox of exponential-time algorithms, parameterized complexity, as well as the related hardness theories.
More information on the topics to be covered appears in the schedule below (which will be updated during the semester).
The course consists of 10 lectures of 1.5 hours
The final grades for the course will be based on homework assignments. There will be no exam.
| Lecture No. | Date | Topic | Notes |
|---|---|---|---|
| 1 | 28/1 | Branching Algorithms | notes |
| 2 | 30/1 | Kernelization | homework 2, notes |
| 3 | 4/2 | Randomized Algorithms | homework 3, notes |
| 4 | 6/2 | Iterative Compression | homework 4, notes |
| 5 | 11/2 | Inclusion-Exclusion | homework 5 |
| 6 | 13/2 | Exponential Time Hypothesis | notes, |
| 7 | 18/2 | Parameterized Hardness | notes, |
| 8 | 20/2 | More hardness | Lec. 7 continued, homework 6 (with solution) |
| 9 | 25/2 | Structural Parameters/Treewidth/DP | notes |
| 10 | 27/2 | Local Search |