direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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

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 3-6 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 semi-randomly. 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

There will be a 30-minute oral exam after the end of the semester, scheduled on one of two possible dates: either Monday, February 18 or Monday, March 18. Please register for one of these two options during one of the lectures or exercises. For the exam itself, please register at the Prüfungsamt by bringing the yellow registration form with you at the day of the exam (or beforehand). Also see the notes above for prerequisites you need to fulfill for being admitted to the exam. 

Exam schedule
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 n-cube 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 i-lexical matchings (0<=i<=n) are indeed edge-disjoint 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; non-crossing perfect matchings on a convex set of 2n points; non-crossing partitions of a convex set of n points; 132-avoiding 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 2n-6.

  • Dec 06: No class
  • Dec 12: Geometric flip graphs: non-crossing perfect matchings [Hernando, Hurtado, Noy: Graphs of non-crossing 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 c1,...,cn 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 j-cj+s in the permutation, where s is the number of indices k>j with ck=k-1. 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 (star-like 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 pattern-avoiding families of permutations (231-avoiding, {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 all-right 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:

Contact Information

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.