## Combinatorial Search, Spring 2008

###
Lecturers

Peter Bro Miltersen,
Troels Bjerre Sørensen,
and Kristoffer Arnsfelt Hansen.
### Lectures

- Tuesdays, 12.15-14.00, Lille Auditorium, Aabogade 15
- Thursdays, 12.15-13.00, Lille Auditorium, Aabogade 15

### 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 or 2006 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*.
The three questions on the
exam will be: - 1.
**P, NP, NPC; Cook's theorem.**
- 2.
**NP-complete problems. **
- 3.
**Approximation algorithms and heuristics.**

### Excercise classes

You can
switch classes if and only if you can find someone to switch with.
Please use the daimi newsgroup `daimi.dSoegOpt` for this.
- Class 1: Monday 12-15, Codd 121. Classes: April 21,
**28**, May 5, **19**,
**26**, June 2. T.A.: Peter Dueholm Justesen.
- Class 2: Tuesdays 9-12, Shannon 157. Classes: April 22,
**29**, May 6,
**13**, 20, **27**. T.A.: Rocio Santillan Rodriguez.
- Class 3: Thursday 9-12, Shannon 159. Classes: April 17,
**24**, May 8, **15**,
22, **29** T.A: Rocio Santillan Rodriguez.

Dates in bold are dates when solutions to compulsory problems are to
be
handed in.
### Compulsory Problem 1:

*P, NP and NPC, Exercise 4*. Bonus
question: Is it necessary to assume that the representations are good?
Hand in at the
exercise classes on April 24, 28, 29. Since students in the
class of April 24 does not get as much time as promised, they can make
special arrangements with their teaching assistant to hand in the
problem later (but before May 1st). They still have to hand it in in person.
### Compulsory Problem 2:

Pdf. Hand in
at the exercise classes on May 13,15,19.
### Compulsory Problem 3:

Pdf. Hand in
at the exercise classes on May 26,27,29.
### Exercises

- Problems for April 17,21,22
- Problems for April 24,28,29
- Problems for May 5,6,8
- Problems for May 13,15,19
- Problems for May 20,22,26
- Problems for May 27,29, June 2

### Literature

**Combinatorial Search, F08, Kompendium. ** is available at
GAD.
- 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.

### Lectures

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