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

Previous years: [Spring 2006]


Current

  • [7 Dec 2006] 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 21 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 Wed 13 Dec and close Wed 3 Jan.
  • [4 Nov 2006] The third programming assignment has been published. Deadline for returning the solutions is 23 November. For further information please contact the course assistant, Antti Rusanen.
  • [19 Oct 2006] The second programming assignment has been published. Deadline for returning the solutions is 9 November. For further information please contact the course assistant, Antti Rusanen.
  • [5 Oct 2006] The first programming assignment has been published. Deadline for returning the solutions is 19 October. For further information please contact the course assistant, Antti Rusanen.
  • [10 Aug 2006] First lecture Thu 14 Sep, room TB353. Registration via TOPI.


General

  • Lectures: Ilkka Niemelä and Pekka Orponen, 14 Sep - 7 Dec, Thu 14-16, room TB353.
  • Tutorials: Antti Rusanen, 21 Sep - 7 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 21 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

Week Date Topic Lecture slides
37.Sep 14 Course arrangements and overview of contents. Postscript PDF
38.Sep 21 Combinatorial search and optimisation problems. Postscript PDF
39.Sep 28 Complete search methods. Postscript PDF
40.Oct 5 Local search techniques. Postscript PDF
41.Oct 12 Constraint satisfaction: formalisms and modelling. Postscript PDF
42.Oct 19 Constraint satisfaction: algorithms. Postscript PDF
43.Oct 26 Exam week: no lecture.
44.Nov 2 Constraint satisfaction: global constraints, local search
Linear and integer programming: formalism.
Postscript PDF
45.Nov 9 Linear and integer programming: modelling and tools. Postscript PDF
46.Nov 16 Linear and integer programming: algorithms. Postscript PDF
47.Nov 23 Genetic algorithms. Postscript PDF
48.Nov 30 Novel methods. Postscript PDF
49.Dec 7 Complexity of search. Postscript 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 Spring 2006.
  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 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 19 October. For further information please contact the course assistant, Antti Rusanen.
  • The second programming assignment has been published. Deadline for returning the solutions is 9 November. For further information please contact the course assistant, Antti Rusanen.
  • The third programming assignment has been published. Deadline for returning the solutions is 23 November. For further information please contact the course assistant, Antti Rusanen.

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.
  • 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: 04 October 2007.