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 
2Oct2023 
PDF 
Second series 
16Oct2023 
PDF (v2) PDF (old) 
Third series 
30Oct2023 
PDF 
Fourth series 
13Nov2023 
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 TheoremProving Procedures from 1971 contains the proof that SAT is NPcomplete

Another proof of Cook's theorem by Richard Lipton

Famous book on NPcompleteness by Garey and Johson: Computers and Intractability: A Guide to the Theory of NPCompleteness

Richard Karp's landmark paper Reducibility Among Combinatorial Problems showed that 21 diverse combinatorial and graph theoretical problems are NPcomplete.

Richard Lipton: Is P=NP an Ill Posed Problem?

Gerhard Woeginger's "PversusNP" page

Nice movie on Youtube explaining PversusNP in very accessible way

The game that led to Hamiltonian cycles

Lots of information on the TSP.

A nice instance of SUBSETSUM (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 LProunding results for MaxSatisfiability.

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: NPcomplete Problems and Physical Reality

Video of the EURO2018 Keynote by Gerhard Woeginger on Σ_{2}P.
Updated on 10th of October, 2023 by Paul Bouman (based on previous versions by G.J. Woeginger, J. Nederlof and Marie Schmidt)