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 2008

The course T-79.5202 replaces the course T-79.161 Combinatorial Algorithms and is lectured by D.Sc. (Tech.) Harri Haanpää in Spring 2008 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.



Lectures (sketch)

The lectures will take place on Jan 23, Jan 30, Feb 6, Feb 13, Feb 27, Mar 5, Mar 19, Apr 2, Apr 16, Apr 23 and possibly Apr 30.

The lectures are not likely to take place on Feb 20 (winter holiday), Mar 12 (exam week), Mar 26 (Easter holiday), or Apr 9 (lecturer on a work-related trip). Changes may occur.

The lecture schedule below will require some adjustments and is provided for information purposes only without any guarantee.

  1. (Jan 23) ranking and unranking subsets, Gray codes; home assignment 1
  2. (Jan 30) backtracking, maximum clique, exact cover; permutations, even and odd permutations, their lexicographical rank
  3. (Feb 6) Trotter-Johnson and Myrvold-Ruskey rank and unrank of permutations, branch and bound
  4. (Feb 13) heuristic methods; integer partitions; home assignment 2
  5. (Feb 27) feedback on home assignment 1; heuristic methods continued; Prüfer correspondence, Catalan numbers
  6. (Mar 5) isomorphisms, groups, subgroups, orbits, transversals
  7. (Mar 19) feedback on home assignment 2; groups continued, orderly algorithm; home assignment 3
  8. (Apr 2) canonical parent method, canonical augmentation method, certificates for graphs
  9. (Apr 16) certificates for trees and graphs, Schreier-Sims representation of groups
  10. (Apr 23) generating structures with prescribed automorphisms, review


[Spring 2007] [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: 22 May 2008. Harri Haanpää (haha©