Combinatorial Search, Spring 2008

Lecturers

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

Lectures

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:

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

Literature

Curriculum ("Pensum")

Lectures