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


Exercise classes

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


Compulsory problems


Curriculum ("Pensum")

Exam lists

Exam questions

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