Exercise sheet #5
The fourth exercise sheet is available here. The deadline is February 1.
Exercise sheet #4
The fourth exercise sheet is available here. The deadline is January 18.
No lecture on January 4
As it was announced during the last lecture, there will be no lecture on January 4, 2022.
Exercise sheet #3
The third exercise sheet is available here. The deadline is December 07.
Exercise sheet #2
The second exercise sheet is available here. The deadline is November 16.
Exercise sheet #1
The first exercise sheet is available here. The deadline is November 2.
The Zoom link for the lecture (starting 10:15 on every Tuesday):
This course is about designing fast algorithms for NP-hard graph theoretic problems, where the running time depends on multiple parameters of the input. For example, while a database may contain a very large amount of data, the size of the database queries is typically extremely small in comparison. The aim would be to obtain algorithms that have a small dependence on the database size, but possibly a larger dependence on the query size. Such an algorithm would be fast when the queries are small.
We will see several algorithmic techniques to design fast algorithms for NP-hard problems in this setting, called Fixed Parameter Tractable (FPT) algorithms, as well as an overview of the lower-bound methods. We will also learn about preprocessing or data-reduction algorithms in this setting, called Kernelization algorithms, which run in polynomial time and reduce a given instance of a NP-hard problem to an equivalent but much smaller instance.
Two hours of lectures every week and two hours of tutorials every other week.
Lectures: Tuesday, 10:15-12:00, online over Zoom
First lecture: October 19, 2021
Basic knowledge of algorithms, graph theory and probability will be assumed.
|Date||Topic||Material||Reference (see below)||Exercise||Due|
|October 19||L01: Introduction I||Slides Video||1, 3.1, 3.2, 3.3|
|October 26||L02: Introduction II||Slides Video||2.1, 2.2.1, 3.5, 5.1, 5.2||Sheet 1||November 02|
|November 02||L03: Introduction III||Slides Slides Video||4, 6.1|
|November 09||L04: Lower bounds||Slides Video||13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3||Sheet 2||November 16|
|November 16||L05: Kernelization I||Slides Video||2.1,2.2, 2.6|
|November 23||L06: Kernelization II||Slides Video||2.3.1,2.4, 2.5|
|November 30||L07: Kernelization III||Slides Slides Video||9.1,15.1,15.2.2||Sheet 3||December 07|
|December 07||L08: Algebraic Methods||Slides (slide 19 has been updated)Video||10.1.1,10.1.2,10.4.1|
|December 14||L09: Representative sets and matroids||Slides Video||12.1, 12.1.1, 12.1.2, 12.1.3, 12.3, 12.3.1, 12.3.2||No sheet|
|January 11||L10: Important Cuts||Slides Video||8.1, 8.2, 8.3, 8.5, 8.6||Sheet 4||January 18|
|January 18||L11: Treewidth I||Slides Video||7.1-7.4|
|January 25||L12: Treewidth II||Slides Video||11.2.1,14.5.2, 13.6.2||Sheet 5||February 1|
|February 01||L13: Treewidth III||Slides Video||7.7|
|February 08||L14: Turing and Lossy Kernelization||Slides Slides Video||9.4, 23.1 and 23.4 from this book|
"Parameterized Algorithms" by Cygan et al. (see this for free pdf of the book from the authors).