Combinatorial Search, Spring 2009
Peter Bro Miltersen,
and Kristoffer Arnsfelt Hansen.
About the course
The course consists of three hours of lectures and and three hours
of exercise classes each week, throughout the fourth quarter (second
half of spring semester). The exam is an oral exam without preparation,
with grading according to the 7-scale. Each examination is 30 minutes
including evaluation and other "overhead". Each student must hand
solutions to three compulsory assignments in order to take the
exam. They should be completed individually (in Danish or English), but
disucssions on the assignments are allowed and encouraged.
The solutions should be given to the teaching assistant in person
at specific exercise classes.
If you passed the compulsory program
in the course of 2005, 2006, 2007, 2008 it can be transferred to this course,
but please send me an email requesting such a transfer as
early as possible and before May 1st.
- 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 ()
- 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
- 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
- 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
Slides in ppt, pdf.
- May 20. (PBM) Approximation algorithms. Read: Cormen et al. The
analysis of set cover is much simplified in this
Slides in ppt
- May 22. (PBM) Approximation heuristics. Read: Johnson and McGeoch, pages
- May 27. (PBM) Approximation heuristics. Read: Johnson and McGeoch, pages
- May 29. (PBM) Approximation heuristics. Read. Johnson and McGeoch, pages 261-