- Wednesdays, 14.15-16.00, Lille Auditorium, Aabogade 15
- Fridays, 12.15-13.00, Lille Auditorium, Aabogade 15

- Monday 11-14 in Shannon 164. TA: Daniel Andersson ()
- Thursday 8-11 in Shannon 164. TA: Rocio Santillan ()
- Thursday 11-14 in Shannon 164. TA: Thomas Dueholm Hansen ()

- Problems for first class
- Problems for second class
- Problems for third class
- Problems for fourth class
- Problems for fifth class
- Problems for sixth class

*Compulsory Problem 1, hand in to teaching assistant April 30th or May 4th.*. Let 3COLOUR be the problem of deciding if the vertices of an undirected graph can be coloured with three colours so that no two adjacent vertices share a colour. Construct a polynomial reduction from 3COLOUR to SAT without appealing to Cook's theorem.*Compulsory Problem 2, hand in to teaching assistant May 14th or May 18th.*Pdf.*Compulsory Problem 3, hand in to teaching assistant May 25th or May 28th.*Pdf.

**Combinatorial Search, F09, Kompendium.**will be available at GAD after easter.- Virtual handout: P, NP and NPC.

- Peter Bro Miltersen, P, NP and NPC
- Christos H. Papadimitriou, Computational Complexity, pages 181-206.
- T.H. Cormen, C.E. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms second edition, pages 1022-1043..
- D.S. Johnson and L.A. McGeoch, The traveling salesman problem: a case story, pages 215-241, 246-273, 286-305, 309-310.
- Kristoffer Arnsfelt Hansen, The set covering problem (supplemental note).

- P, NP and NPC.
- Cook's theorem and the complexity of variants of SAT.
- NP-complete graph problems.
- NP-complete problems involving sets and numbers.
- Approximation algorithms.
- Local search heuristics for TSP.

- April 3 (PBM). Formal languages. The Turing machine
model.
**P**. Read: P, NP and NPC, pages 1-4. Slides, pdf. - April 15 (PBM).
**NP**and**NPC**. Read: P, NP and NPC, pages 5-14. Slides, pdf. - April 17 (PBM). Representations of Boolean functions. Truthtables, formulas, circuits. CNFs and DNFs. SAT and Circuit SAT. Read: P, NP and NPC, pages 14-16,. Slides, pdf.
- April 22 (KAH). Cook's theorem. P, NP and NPC, pages 16-. Slides.
- April 24 (KAH). NP-completeness of variants of SAT. Read: Papadimitriou, 181-188
- April 29 (KAH). NP-complete problems. Read: Papadimitriou, 188-199.
- May 1 (KAH) NP-complete problems. Read: Papadimitriou, 188-199.
- May 6 (KAH). NP-complete problems. Read: Papadimtriou, 199-203.
- May 13 (KAH). NP-complete problems involving numbers. Read: Papdimitriou, 202-206. Slides.
- May 15 (PBM). Approximation algorithms. Read: Cormen et al. Slides: Slides in ppt, pdf.
- May 20. (PBM) Approximation algorithms. Read: Cormen et al. The analysis of set cover is much simplified in this note. Slides in ppt
- May 22. (PBM) Approximation heuristics. Read: Johnson and McGeoch, pages 215-228. Slides.
- May 27. (PBM) Approximation heuristics. Read: Johnson and McGeoch, pages 230-261.
- May 29. (PBM) Approximation heuristics. Read. Johnson and McGeoch, pages 261-