Current events

• [May 21]Grades published
• [Mar 20]Third homework assignment published; deadline April 25.
• [Feb 12]Second homework assignment published; deadline March 14.
• [Feb 9] Everyone should have received e-mail about peer reviewing 1st home assignments.
• First tutorial: 23 Jan, 14-15, B353.
• First lecture on 15 Jan.
• First homework assignment published at first lecture; deadline Feb 7.
• Registration by WWWTopi.

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

• Lectures: in English by D.Sc.(Tech.) Harri Haanpää, (Mondays starting January 15 from 13 to 15 in room TB353)
• Exercises: Aleksi Hänninen, Tuesdays starting January 23 from 14 to 15 in room TB353
• Course's unofficial IRC channel: #T-79.5202
• 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 2006, May 2007.

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

Lectures (sketch)

• Lecture 1 (Jan 15): ranking and unranking subsets, Gray codes; home assignment 1
  
• Lecture 2 (Jan 22): backtracking, maximum clique, exact cover
• Lecture 3 (Jan 29): permutations, even and odd permutations, lexicographical, Trotter-Johnson and Myrvold-Ruskey rank and unrank
• Lecture 4 (Feb 5): branch and bound
• Lecture 5 (Feb 12): feedback from home assignment 1; heuristic methods; home assignment 2
  
• No lecture on Feb 19
• Lecture 6 (Feb 26): heuristic methods continued
• No lecture on Mar 5
• Lecture 7 (Mar 12): integer partitions, Prüfer correspondence, Catalan numbers
• Lecture 8 (Mar 19): feedback from home assignment 2; home assignment 3; isomorphisms, groups
• Lecture 9 (Mar 26): subgroups, orbits, cosets, transversals
• Lecture 10 (Apr 2): orderly algorithm, canonical parent method
• No lecture on Apr 9
• Lecture 11 (Apr 16): Canonical augmentation method, certificates for trees and graphs
• Lecture 12 (Apr 23): Burnside's Lemma, Schreier-Sims representations of groups, generating structures with prescribed automorphisms

Archives

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