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)

Spring 2006

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]

Current

  • [4 May 2006] Please provide feedback on the course via the DCSE department's course feedback system. The electronic questionnaires open Fri 5 May and close Mon 22 May.
  • [4 May 2006] The course exam is on Monday 15 May, 9--12 a.m. Check the time and place still from the departmental exam schedule, and remember to register for the exam via TOPI by Wed 10 May.
  • [4 Jan 2006] First lecture Thu 19 Jan, room TB353. Registration via TOPI.

General

  • Lectures: Ilkka Niemelä and Pekka Orponen, 19 Jan - 4 May, Thu 10-12, room TB353.
  • Tutorials: Antti Rusanen, 20 Jan - 5 May, Fri 10-12, 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 Mon 15 May, registration by TOPI. Check exact time and place from the DCSE department exam schedule.
  • Grading: Exam max 50 points, programming assignments max 3*2 = 6 points, tutorials max 4 points, total 60 points. For the programming assignments, a correctly functioning program, returned on time with appropriate work description yields 2 points; each revision round deducts 1 point from maximum. For the tutorials, credit is awarded from problem set 3 onwards.

Lecture schedule (tentative)

Week Date Topic Lecture slides
3.Jan 19 Course arrangements and overview of contents. Postscript PDF
4.Jan 26 Combinatorial search and optimisation problems. Postscript PDF
5.Feb 2 Search spaces and objective functions. Complete vs. local search. Postscript PDF
6.Feb 9 Further local search techniques. Postscript PDF
7.Feb 16 Constraint satisfaction: formalisms and modelling. Postscript PDF
8.Feb 23 Constraint satisfaction: algorithms. Postscript PDF
9.Mar 2 No lecture.
10.Mar 9 Exam week: no lecture.
11.Mar 16 Constraint satisfaction: global constraints, local search
Linear and integer programming: formalism.		 Postscript PDF
12.Mar 23 Linear and integer programming: modelling and tools. Postscript PDF
13.Mar 30 Linear and integer programming: algorithms. Postscript PDF
14.Apr 6 Genetic algorithms. Postscript PDF
15.Apr 13 Easter vacation: no lecture.
16.Apr 20 Novel methods. Postscript PDF
17.Apr 27 Complexity of Search. Postscript PDF
18.May 4 Review and discussion of the course material. Feedback.

Tutorial problems

The weekly problem sets will be available here as the course progresses.
  1. Problem set 1: ps, pdf
  2. Problem set 2: ps, pdf
  3. Problem set 3: ps, pdf
  4. Problem set 4: ps, pdf
  5. Problem set 5: ps, pdf
  6. Problem set 6: ps, pdf
  7. Problem set 7: ps, pdf
  8. Problem set 8: ps, pdf
  9. Problem set 9: ps, pdf
  10. Problem set 10: ps, pdf
  11. Problem set 11: ps, pdf
  12. Problem set 12: ps, pdf

Programming assignments

There will be three small programming assignments using Java. The details will be announced later, but the aim is to gain hands-on experience with the techniques learned in the course. The first set of assignments will be handed out on 10 Feb, the second on 24 Feb, and the third on 24 Mar. 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.

Descriptions of the programming tasks, input formats, and the programming environment are available here.

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. Cambrigde 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.
  • H. H. Hoos, T. Stützle, Stochastic Local Search: Foundations and Applications. Morgan Kaufmann (Elsevier), Amsterdam, 2005.
  • 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:
  • Karl Sims' homepage. (Contains links to the "Evolved Virtual Creatures" animation and paper.)
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 06 June 2006.