## T-79.4201 Search Problems and Algorithms (4 cr)## Spring 2006The 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)
## Tutorial problemsThe weekly problem sets will be available here as the course progresses.- 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
## Programming assignmentsThere 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- Tentti/exam 15.5.2006: tehtävät (pdf), problems (pdf), tulokset/results.
## Course materialThe 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 linksSome 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. |