Introduction (March 22, 2021).
Parameterized Algorithms (April 5, 2021).
Treewidth (April 12, 2021). These lecture notes are from a previous course. They are included in full in case there are students who wish to read this full version. In this course we went over Section 2, Section 3 (without proof of Proposition 4 and without Theorem 7), and Section 4 (up to and not including Section 4.1, and skipping over some stuff in the middle of page 6).
Spectral graph theory. (May 24, 2021).
Semi-random planted clique, lecture and homework. (June 7, 2021).
The Ellipsoid algorithm. (June 14, 2021). These lecture notes are from a previous course.
Additional notes on planted clique and independent set. (June 28, 2021).
Smoothed analysis of the knapsack problem. (July 5, 2021). Slightly updated on July 19.
The secretary problem. (July 5, 2021).
Homework 1 (hand in by April 12). The two questions on slide 38 (FIFO online paging), and the question on slide 43 (Perceptron algorithm). Hints can be found (with different notation) in exercises 1.4, 1.5 and 1.7 in the BWCA book.
Homework 2 Parametrized Algorithms. (April 12, hand in by April 26).
Homework 3 Approximation Stability and Perturbation Resilience. (May 3, hand in by May 24).
Homework 4 Spectral graph theory. (May 24, hand in by June 7).
Homework 5 Semi-random planted clique, lecture and homework. (June 7, hand in by June 21).
Hint for homework 5 Perfect matchings in random bipartite graphs.
Homework 6 Embeddings, Ellipsoid, Combinatorial Smoothed Analysis . (June 28, hand in by July 12).
Final exam. Hand in by 14:15, Friday July 23.