|
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]
- [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.
- 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.
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 |
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.
- Problem set 1: ps, pdf
- Problem set 2: ps, pdf
- Problem set 3: ps, pdf
- Problem set 4: ps, pdf
- Problem set 5: ps, pdf
- Problem set 6: ps, pdf
- Problem set 7: ps, pdf
- Problem set 8: ps, pdf
- Problem set 9: ps, pdf
- Problem set 10: ps, pdf
- Problem set 11: ps, pdf
- Problem set 12: ps, pdf
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.
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.)
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.
|