Current events

• Preliminary results of Spring 2006 course. For an opportunity to review the grading please contact the lecturer by Friday 26 May.
• Results of 2nd home assignment
• 3rd homework assignment published, due date Apr 19.
• Results of 1st home assignment
• 2nd homework assignment published, due date Mar 15
• Irc channel #T-79.5202 created for the course. The channel may be password-protected; in that case use the same password you use to access the home assignments on the WWW.
• 1st homework assignment published, due date Feb 8
• Exercise sessions cancelled at least until further notice

T-79.5202 Combinatorial Algorithms (4 cr) P

Spring 2006

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 2006 in Teaching Periods III (January 16 – March 3) and IV (March 12 – May 5).

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 simulatulated 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: D.Sc.(Tech.) Harri Haanpää, (Mondays starting January 16 from 2 p.m. to 4 p.m. in room TB353)
• Exercises: N.N., not arranged until further notice
• 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: 19 May 2006 and ?? October(?) 2006.

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

• 16.1. Lecture 1: ranking and unranking subsets, Gray codes; home assignment 1
  
• 23.1. Lecture 2: backtracking, maximum clique, exact cover
• 30.1. Lecture 3: permutations, even and odd permutations, lexicographical, Trotter-Johnson and Myrvold-Ruskey rank and unrank
• 6.2. Lecture 4: branch and bound
• 13.2. Lecture 5: feedback from home assignment 1; heuristic methods; home assignment 2
  
• 20.2. NO LECTURE
  
• 27.2. Lecture 6: heuristic methods continued
• 6.3. NO LECTURE (exam week)
• 13.3. Lecture 7: integer partitions, Prüfer correspondence, Catalan numbers
• 20.3. Lecture 8: feedback from home assignment 2; home assignment 3; isomorphisms, groups
• 27.3. Lecture 9: subgroups, orbits, cosets, transversals
• 3.4. Lecture 10: orderly algorithm, canonical parent method
• 10.4. Lecture 11: Canonical augmentation method, Schreier-Sims
• 17.4. NO LECTURE (Easter)
• 24.4. Lecture 12: Feedback from home assignment 3; generating structures with prescribed automorphisms
• 1.5. NO LECTURE (Vappu)

Archives