TCS / Studies / T-79.5202 Combinatorial Algorithms
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Current events

T-79.5202 Combinatorial Algorithms (4 cr) P

Spring 2007

The course T-79.5202 replaces the course T-79.161 Combinatorial Algorithms and will be lectured by D.Sc. (Tech.) Harri Haanpää in Spring 2007 in Teaching Periods III and IV.

As the world becomes more and more digital the importance of combinatorial algorithms is growing rapidly. Everyone who designs algorithms in his work runs into problems where they are needed. It is no coincidence that the next book by Donald Knuth, (Vol. 4A-4C, estimated publication 2007-2010) in the series The Art of Computer Programming is Combinatorial Algorithms.

On the course Combinatorial Algorithms the focus is on the most important combinatorial structures, such as graphs and subsets, and algorithms with which they can be handled efficiently. Additionally methods such as backtrack search, tabu search and simulated annealing are used in searching for a combinatorial structure with desired properties. Further, symmetries are used to limit the size of the search.

After the course the student shall:

  1. understand fundamental combinatorial structures (graphs, permutations, etc.).
  2. understand the most important handling algorithms for fundamental combinatorial structures
  3. know the most common search methods and be able to apply them to practical problems
  4. understand the concept of symmetry and the connection between symmetries and permutation groups; be able to use symmetries to limit the search
  5. be able to take on computationally difficult (e.g. NP-complete) combinatorial problems by using stochastic methods (such as tabu search, simulated annealing).

The content of the course corresponds with research topics of the Computational Complexity and Combinatorics group of the Laboratory for Theoretical Computer Science and is very suitable also for postgraduate students.

The course T-79.5203 Graph Theory is closely related.

Arrangements

Material

Lectures (sketch)


Archives

[Spring 2006]

The course was previously known under the course code T-79.161.


[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 21 May 2007. Harri Haanpää (haha©tcs.hut.fi)