Page Content
to Navigation
Combinatorial Algorithms (ADM III)
Lecture number: 3236 L 064
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).
Schedule
Day  Time  Room  

Lecture  Wednesday  08:30  10:00  MA 644 
Lecture  Thursday  12:15  13:45  MA 651 
Exercises will be integrated into the normal lecture schedule. We will have an exercise class every second week or so, 6 exercise classes in total, with roughly 36 problems to be prepared and solved by the students. At the beginning of the exercise classes, all students are asked to specify the problems they solved and are ready to present in front of the class. The students who actually present a solution are then selected semirandomly. In the course of the entire semester, each student has to solve 12 such problems to be admitted to the exam (the students only have to declare having solved 12 problems satisfactorily, not necessarily present all 12 solutions).
Exam
Feb 18  Mar 18  

10:00  Daniel O.  10:00  Armin F. 
10:35  Max Z.  
11:10  Marcel B.  
11:45  Tomohivo K.  
12:20  Carla S. 
The exam takes place in MA 520.
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], Monotone Gray codes [Knuth Sec. 7.2.1.1]
 Oct 31: Exercise class: [Ruskey Sec. 5.14: Problem 5, Problem 7, Problem 10, Problem 11], [Knuth Sec. 7.2.1.1: Problem 7, Problem 17]
 Nov 01: Monotone Gray codes [Knuth Sec. 7.2.1.1]
 Nov 07: Balanced Gray codes [Knuth Sec. 7.2.1.1]
 Nov 08: Generating combinations [Gregor, Mütze: Trimming and gluing Gray codes]
 Nov 14: Generating combinations
 Nov 15: Exercise class: [Knuth Sec. 7.2.1.1: Problem Problem 44, Problem 49, Problem 50, Problem 52, Problem 55, Problem 58]
 Nov 21: Proof of the middle levels theorem [Gregor, Mütze, Nummenpalo: A short proof of the middle levels theorem]
 Nov 22: Proof of the middle levels theorem
 Nov 28: Geometric flip graphs: triangulations [Hurtado, Noy: Graph of triangulations of a convex polygon and tree of triangulations]
 Nov 29: Geometric flip graphs: triangulations
 Dec 05: Exercise class
 Problem 1:Compute (explicitly) the difference in size between the two partition classes of the subgraph of the ncube induced by all bitstrings with at least k and at most l many 1s, for all 0<=k<=l<=n.
 Problem 2:Prove that the family of ilexical matchings (0<=i<=n) are indeed edgedisjoint perfect matchings in the subgraph of the (2n+1)cube induced by all bitstrings with n or n+1 many 1s (i.e., the middle levels graph; recall the definitions in Section 2 in the paper linked under Nov 21).
 Problem 3:Establish bijections between the following classes of objects counted by the Catalan numbers: Dyck paths of length 2n; ordered rooted trees with n edges; full binary trees with n+1 leaves; triangulations of a convex set of n+2 points; noncrossing perfect matchings on a convex set of 2n points; noncrossing partitions of a convex set of n points; 132avoiding permutations of {1,...,n}.
 Problem 4:Prove that the flip graph of triangulations of a convex set of n points under edge flips has diameter at most 2n6.
 Dec 06: No class
 Dec 12: Geometric flip graphs: noncrossing perfect matchings [Hernando, Hurtado, Noy: Graphs of noncrossing perfect matchings]
 Dec 13: Generating permutations (Algorithm L, Algorithm P) [Knuth Sec. 7.2.1.2]
 Dec 19: No class
 Dec 20: No class
 Jan 09: Exercise class
 Problem 1:Prove that the flip graph of permutations given by adjacent transpositions is bipartite.
 Problem 2:Given the inversion table c_{1},...,c_{n} of a permutation, show how to reconstruct the permutation from it. Prove that in step P5 of Algorithm P, the element j is located at position jc_{j}+s in the permutation, where s is the number of indices k>j with c_{k}=k1. Argue that s<=2.
 Problem 3:Show that the following greedy algorithm generates all permutations by adjacent transpositions in the same order as Algorithm P: Start with the identity permutation 1,...,n. In each step, swap the largest possible element x with one of its neighbors, such that we arrive at a permutation that has not been encountered before. Argue why the left or right neighbor with which x is swapped is uniquely determined.
 Problems 4+5:[Knuth Sec. 7.2.1.2: Problem 17, Problem 20]
 Jan 10: Generating permutations (starlike transpositions, Algorithm E, arbitrary transposition trees) [Knuth Sec. 7.2.1.2]
 Jan 16: A general framework for generating natural families of permutations (Algorithm J)
 Jan 17: Generating patternavoiding families of permutations (231avoiding, {231,132}avoiding, binary trees by rotations, BRGC)

Jan 23: Exercise class
 Problem 1:Which other permutations, instead of the identity permutation, can be used as a seed in Algorithm J? Under which condition does the algorithm create a cyclic listing, i.e., one in which the first and last permutation are related by a jump?
 Problem 2:Given two natural families of permutations, prove that their intersection and union is also a natural family.
 Problem 3:Prove that for any integer k, the family of permutations of length n with at most k peaks is natural. A peak in a permutation is a triple of consecutive entries where the biggest entry is in the middle.
 Problem 4:Given a vincular pattern that does not have the largest symbol at its leftmost or rightmost position, and where the largest symbol is underlined (part of the two symbols that must be neighbors), prove that the family of permutations avoiding this pattern is natural. What can you say for patterns where the largest symbol is leftmost or rightmost, or where the largest symbol is not underlined?
 Problem 5:Find an efficient (ideally loopless) algorithm for generating binary search trees on nodes {1,...,n} by rotations based on the ordering given by Algorithm J in the variant for search trees: (1) Start with the allright search tree; (2) Rotate at the largest possible node such that a new tree is generated.
 Jan 24: Generating topological sorts (Algorithm V) [Knuth Sec. 7.2.1.2]
 Jan 30: The twelvefold way [Knuth Sec. 7.2.1.4]
 Jan 31: Generating partitions (Algorithm P and H) [Knuth Sec. 7.2.1.4]
 Feb 06: Generating spanning trees (Algorithm S) [Knuth Sec. 7.2.1.6]
 Feb 07: Exercise class: [Knuth Sec. 7.2.1.2: Problem 95, 96, 97, Sec. 7.2.1.4: Problem 10, 54]
 Feb 13: De Bruijn sequences [Ruskey Sec. 7]
 Feb 14: Don Knuth's Christmas tree lecture 2016 on the history of Hamilton cycles
References
The course is mainly based on the following references:
 Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, AddisonWesley, 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
 Xavier Viennot, The Art of Bijective Combinatorics, online video lectures: http://www.viennot.org/abjccourse.html
 The Combinatorial Object Server Website: http://combos.org
Contact Information
Lecturer: Dr. Torsten Mütze