Combinatorial Search, Spring 2009

Lecturers

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 in satisfactory 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.

Lectures

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

Exercise classes

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 ()

Exercises

Compulsory problems

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.

Literature

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

Curriculum ("Pensum")

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).

Exam lists

Exam questions

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.

Lectures

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-