Current events

• May 22: Course results published.
• Mar 27: Third home assignment published, deadline Friday 25 April.
• Feb 14: Second home assignment published, deadline Friday 14 March.
• Jan 24: First home assignment published, deadline Friday 15 February.

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.

Arrangements

• Lectures: in English by D.Sc.(Tech.) Harri Haanpää, (Wednesdays starting January 23 from 14 to 16 in room TB353)
• Exercises: N.N., Thursdays starting January 24 from 13 to 14 in room TB353
• Schedule tentative!
• Requirements: Exam and three home assignments. Exams will be arranged in May and in the exam period in the middle of the Autumn semester. The home assignments are programming assignments, where the techniques studied on the course can be applied. For each assignment the student must write a short description of the methods used and the results obtained. The home assignments must be completed before taking the exam, and they are valid in the May and October exams of the year when the course is taken.
• Next exams: October, May.

Material

• Literature: D. L. Kreher & D. R. Stinson: Combinatorial Algorithms; Generation, Enumeration & Search, CRC Press, 1998.
• Lecture slides, which will be updated and translated to English as the course progresses; also last Finnish version of lecture slides, no longer updated
• Exercises and home assignments
• Related material and links (send your suggestions)
  • Brian Alspach analyzes shuffling cards (light reading)
  • Excerpts of Volume 4 of The Art of Computer Programming
  • Sloane's On line Encyclopedia of Integer Sequences
  • Exercises on Catalan and Related Numbers
  • Project Euler: mathematical problems that can be solved by little computer programs; many number-theoretical, but also some combinatorial

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

Archives

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