Beyond Worst Case analysis of Algorithms, March 2021 - July 2021

by Uri Feige

Some lecture notes:

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).

Handouts (homework) for course.

Homework 1 (hand in by April 12). The two questions on slide 38, and the question on slide 43. Hints can be found (with different notation) in exercises 1.4, 1.5 and 1.7 in the BWCA book.

Homework 2 (April 12, hand in by April 26).