Page Content
to Navigation
Combinatorial Algorithms (ADM III)
Lecture number: 3236 L 261
Algorithms that generate all objects in a particular combinatorial class appear as core building blocks in a wide range of practical applications. Classical examples are algorithms to generate all graphs of a certain size, all spanning trees of a given graph, all bitstrings of a certain length, all permutations of a given ground set, all partitions of a given number etc. In this lecture we will cover several such algorithms, and introduce the techniques for developing and analyzing them. Some of the material we cover is inspired by Donald Knuth's classical book 'The Art of Computer Programming' Vol. 4A, so if you want to get a taste what this lecture is about, you may want to have a look into this book (available online, see references below).
Contact Information
Lecturer: Dr. Torsten Mütze
Schedule
| Day | Time | Room | |
|---|---|---|---|
| Lecture | Tuesday | 10:15 - 11:45 | MA 749 |
| Lecture | Wednesday | 10:15 - 11:45 | MA 550 |
Exercises will be integrated into the normal lecture schedule when necessary.
Exam
Please register for one of the two options on a first-come first-serve basis, by signing in to the list available at the secretariat Dorothea Kiefer in MA 523 (during office hours, starting from January 04). You also need to register for the exam at the Prüfungsamt, and bring the yellow registration form with you at the day of the exam.
| Feb 14th | March 02nd | April 6th | |||
|---|---|---|---|---|---|
| Rok F. (S) | 14:00 | ||||
| Emanuel H. (K) | 11:35 | Antonia C. (L) | 09:15 | ||
| Margot v.A. (K) | 13:00 | Ivan S. (L) | 09:50 | ||
| Jonas I. (K) | 13:35 | ||||
| Rick G. (K) | 14:10 | Bastian S. (L) | 11:00 | ||
| Antonia A. (F) | 14:45 | Michelle D. (L) | 11:35 | ||
| Sybille M. (F) | 15:20 | Janis B. (L) | 13:00 | ||
| Daniel K. (F) | 15:55 | Adalbert F. (L) | 13:35 | ||
| Paula B. (F) | 14:10 | ||||
| Marie Sophie E. (F) | 14:45 | ||||
| Jan Erik M. (F) | 15:20 | ||||
| Norman H. (F) | 15:55 |
Topics covered in the lectures
- Oct 17: Administrative things, introduction [Ruskey Sec. 1]
- Oct 18: Binary reflected Gray code (BRGC), basic properties [Ruskey Sec. 5.1, 5.2]
- Oct 24: Recursive and loopless BRGC algorithms [Ruskey Sec. 5.2]
- Oct 25: BRGC and Venn diagrams [Ruskey, Weston: A survey of Venn diagrams]
- Oct 31: Public holiday, no class
- Nov 01: Exercise class: [Ruskey Sec. 5.14: 5, 7, 10, 11], [Knuth Sec. 7.2.1.1: 7, 17, 55]
- Nov 07: Monotone Gray codes [Knuth Sec. 7.2.1.1]
- Nov 08: Balanced Gray codes [Knuth Sec. 7.2.1.1]
- Nov 14: Generating combinations [Gregor, Mütze: Trimming and gluing Gray codes]
- Nov 15: Generating combinations
- Nov 21: Exercise class: [Knuth Sec. 7.2.1.1: 44, 49, 50, 51, 52, 58, 71]
- Nov 22: Proof of the middle levels theorem [Gregor, Mütze, Nummenpalo: A short proof of the middle levels theorem]
- Nov 28: Proof of the middle levels theorem
- Nov 29: No class
- Dec 05 (Linda Kleist): Rainbow cycles in flip graphs (permutations, subsets) [Felsner, Kleist, Mütze, Sering: Rainbow cycles in flip graphs]
- Dec 06 (Leon Sering): Rainbow cycles in flip graphs (triangulations, spanning trees, matchings)
- Dec 12: A Gray code for triangulations [Hurtado, Noy: Graph of triangulations of a convex polygon and tree of triangulations]
- Dec 12: A Gray code for non-crossing perfect matchings [Hernando, Hurtado, Noy: Graphs of non-crossing perfect matchings]
- Dec 19: Generating permutations (adjacent transpositions, Algorithm P) [Knuth Sec. 7.2.1.2]
- Dec 20: Generating permutations (star-like transpositions, Algorithm E, arbitrary transposition trees) [Knuth Sec. 7.2.1.2], [Kompel'makher, Liskovets: Sequential generation of arrangements by means of a basis of transpositions]
- Jan 09: Generating topological sorts (Algorithm V) [Knuth Sec. 7.2.1.2]
- Jan 10: The twelvefold way, generating partitions (Algorithm P) [Knuth Sec. 7.2.1.4]
- Jan 16: Generating partitions [Knuth Sec. 7.2.1.4]
- Jan 17: No class
- Jan 23: Generating trees (Algorithm P) [Knuth Sec. 7.2.1.6]
- Jan 24: Generating trees (Algorithm B, Algorithm N) [Knuth Sec. 7.2.1.6]
- Jan 30: Generating trees (Sketch of Algorithms L and S) [Knuth Sec. 7.2.1.6]
- Jan 31: Variations on the Chung-Feller theorem for Dyck paths [Mütze, Standke, Wiechert: A minimum-change version of the Chung-Feller theorem for Dyck paths]
- Feb 06: Proof of minimum-change bijection between Dyck paths, introduction to De Bruijn cycles [Ruskey Sec. 7]
- Feb 07: De Bruijn cycles (algorithm, counting)
- Feb 13: De Bruijn cycles (FKM algorithm)
- Feb 14: Don Knuth's Christmas tree lecture 2016 on the history of Hamilton cycles
References
The course is mainly based on the following books:
- Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Addison-Wesley, preprint versions are available online: http://www.cs.utsa.edu/~wagner/knuth/
- Frank Ruskey, Combinatorial generation, available online: http://www.1stworks.com/ref/ruskeycombgen.pdf
- Albert Nijenhuis and Herbert S. Wilf, Combinatorial algorithms, Academic Press, available online: https://www.math.upenn.edu/~wilf/website/CombinatorialAlgorithms.pdf