Exercises (four series)
(If you have questions, send the lecturer an email or ask on Monday)
Important: comments on the homework.
Exercise series |
Deadline |
PDF |
First series |
2-Oct-2023 |
PDF |
Second series |
16-Oct-2023 |
PDF (v2) PDF (old) |
Third series |
30-Oct-2023 |
PDF |
Fourth series |
13-Nov-2023 |
PDF |
Note:
For those lacking background in algorithms design, we recommend to (at least) browse through the first three chapters of ‘Introduction to Algorithms’ by Cormen, Leiserson, Rivest and Stein.
Extra material
-
Stephen Cook's paper The Complexity of Theorem-Proving Procedures from 1971 contains the proof that SAT is NP-complete
-
Another proof of Cook's theorem by Richard Lipton
-
Famous book on NP-completeness by Garey and Johson: Computers and Intractability: A Guide to the Theory of NP-Completeness
-
Richard Karp's landmark paper Reducibility Among Combinatorial Problems showed that 21 diverse combinatorial and graph theoretical problems are NP-complete.
-
Richard Lipton: Is P=NP an Ill Posed Problem?
-
Gerhard Woeginger's "P-versus-NP" page
-
Nice movie on Youtube explaining P-versus-NP in very accessible way
-
The game that led to Hamiltonian cycles
-
Lots of information on the TSP.
-
A nice instance of SUBSET-SUM (where items can be used multiple times). Can you help the waiter?
-
Some lecture notes by Lex Schrijver on matchings
-
The book by David Williamson and David Shmoys on Approximation Algorithms.
-
The
book of Vijay Vazirani on Approximation Algorithms.
Chapter 16 contains some nice LP-rounding results for Max-Satisfiability.
-
The book
of Rod Downey and Mike Fellows on Parameterized Complexity.
The first three chapters provide a very nice and gentle introduction into the field.
-
Scott Aaronson's Complexity Zoo
-
Scott Aaronson: NP-complete Problems and Physical Reality
-
Video of the EURO2018 Keynote by Gerhard Woeginger on Σ2P.
Updated on 10th of October, 2023 by Paul Bouman (based on previous versions by G.J. Woeginger, J. Nederlof and Marie Schmidt)