TCS / Studies / T-79.4201 Search Problems and Algorithms
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

T-79.4201 Search Problems and Algorithms (4 cr)

Autumn 2007 (periods I and II)

The course provides an introduction to the fundamental concepts, techniques and tools used in dealing with large, weakly structured combinatorial search spaces. The topics covered include: search spaces and search methods; backtracking, local and heuristic search; representing and solving search problems using propositional satisfiability, constraint programming and integer programming techniques.


[Current] [General] [Lectures] [Tutorials] [Assignments] [Exams] [Course material] [Links]

Previous years: [Autumn 2006] [Spring 2006]


Current

  • [17 Dec 2007] The lectures and tutorials for this autumn are over; many thanks for your active participation. The autumn exam for the course is scheduled for Thu 20 Dec, 9-12, in Lecture Hall T1. Please verify the time and place from the DCSE department exam schedule, and remember to register for the exam via TOPI. Also, remember to provide feedback on the course via the department's course feedback system. The electronic questionnaires open Mon 10 Dec and close Mon 7 Jan.
  • [8 Nov 2007] The third programming assignment has been published. Deadline for returning the solutions is 29 November. For further information please contact the course assistant, André Schumacher.
  • [18 Oct 2007] The second programming assignment has been published. Deadline for returning the solutions is 8 November. For further information please contact the course assistant, André Schumacher.
  • [4 Oct 2007] The first programming assignment has been published. Deadline for returning the solutions is 25 October. For further information please contact the course assistant, André Schumacher.
  • [14 Aug 2007] First lecture Thu 13 Sep, room TB353. Registration via TOPI.


General

  • Lectures: Ilkka Niemelä and Pekka Orponen, 13 Sep - 13 Dec, Thu 14-16, room TB353.
  • Tutorials: André Schumacher, 20 Sep - 13 Dec, Thu 16-18, room TB353.
  • Registration by TOPI.
  • Prerequisites: Basic knowledge of problem representations and logic (T-79.1001, T-79.3001); facility in programming, data structures and algorithms (T-106.1220 required, T-106.3100 recommended).
  • Requirements: Examination and three programming assignments.
  • Examination: Scheduled for Thu 20 Dec, registration by TOPI. Check exact time and place from the DCSE department exam schedule.
  • Grading: Exam max 40 points, programming assignments max 3*5 = 15 points, tutorials max 5 points, total 60 points. For the programming assignments, a correctly functioning program, returned on time with appropriate work description yields 3 points; the remaining 2 points are allocated based on an efficiency competition among the submitted programs.

Lecture schedule (tentative)

The preliminary lecture slides linked to the schedule below are from the Autumn 2006 instalment of the course, and will be updated to their current form after each lecture.

Week Date Topic Lecture slides
37.Sep 13 Course arrangements and overview of contents. PDF
38.Sep 20 Combinatorial search and optimisation problems. PDF
39.Sep 27 Complete search methods. PDF
40.Oct 4 Local search techniques. PDF
41.Oct 11 Constraint satisfaction: formalisms and modelling. PDF
42.Oct 18 Constraint satisfaction: algorithms. PDF
43.Oct 25 Exam week: no lecture, no tutorial session.
44.Nov 1 Constraint satisfaction: global constraints, local search
Linear and integer programming: formalism.
PDF
45.Nov 8 Linear and integer programming: modelling and tools. PDF
46.Nov 15 Linear and integer programming: algorithms. PDF
47.Nov 22 Genetic algorithms. PDF
48.Nov 29 Novel methods. PDF
49.Dec 6 Independence day: no lecture, no tutorial session.
50.Dec 13 Complexity of search. PDF


Tutorial problems

The weekly problem sets will be available here as the course progresses. The problem sets are likely to be quite similar to those in Autumn 2006.

Programming assignments

There will be three small programming assignments using Java. The aim is to gain hands-on experience with the techniques learned in the course.
  • The first programming assignment has been published. Deadline for returning the solutions is 25 October. For further information please contact the course assistant, André Schumacher.
  • The second programming assignment has been published. Deadline for returning the solutions is 8 November. For further information please contact the course assistant, André Schumacher.
  • The third programming assignment has been published. Deadline for returning the solutions is 29 November. For further information please contact the course assistant, André Schumacher.
The first set of assignments will be handed out on 4 Oct, the second on 18 Oct, and the third on 8 Nov. A functioning program for each of the assignments must be developed personally by each participant and submitted, together with a brief description of the solution method used, by e-mail to the tutorial assistant within three weeks of the hand-out date.


Exams


Course material

The course does not follow any existing textbook. Here are some pointers to general literature covering material discussed at the lectures in more depth:
  • E. Aarts, J. K. Lenstra (Eds.), Local Search in Combinatorial Optimization. J. Wiley & Sons, Chichester UK, 1997.
  • Krzysztof R. Apt: Principles of Constraint Programming. Cambridge University Press, 2003. Book contents.
  • T. Bäck, Evolutionary Algorithms in Theory and Practice. Oxford University Press, 1996.
  • D. Corne, M. Dorigo, F. Glover (Eds.), New Ideas in Optimization. McGraw-Hill, London, 1999.
  • A. E. Eiben, J. E. Smith, Introduction to Evolutionary Computing. Springer-Verlag, Berlin Heidelberg, 2003.
  • H. H. Hoos, T. Stützle, Stochastic Local Search: Foundations and Applications. Morgan Kaufmann (Elsevier), Amsterdam, 2005.
  • W. Michiels, E. Aarts, J. Korst, Theoretical Aspects of Local Search. Springer-Verlag, Berlin Heidelberg, 2007.
  • M. Mitchell, An Introduction to Genetic Algorithms. The MIT Press, Cambridge MA, 1996.
  • C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, 1982. (Reprinted by Dover, Mineola NY, 1998.)

Miscellaneous links

Some links to material related to topics discussed in course:
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 12 May 2008.