SubjectsSubjects(version: 901)
Course, academic year 2022/2023
  
Combinatorial generation: graphs, structures, and algorithms - NTIN112
Title: Kombinatorické generování: grafy, struktury a algoritmy
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: English
Teaching methods: full-time
Guarantor: Torsten Mütze, Ph.D.
doc. Mgr. Petr Gregor, Ph.D.
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: RNDr. Jan Hric (23.03.2022)
In computer science and mathematics we frequently encounter different kinds of combinatorial objects, such as bitstrings, permutations, partitions, binary trees, triangulations, spanning trees, perfect matchings etc. A recurring problem of interest is to exhaustively generate all the objects from a class, each object exactly once. We discuss algorithms for that task, and we will introduce the techniques for developing and analyzing them. We touch upon related questions, such as combinatorial counting and random sampling, including methods from graph theory, order theory, geometry and algebra.
Course completion requirements -
Last update: doc. Mgr. Petr Gregor, Ph.D. (30.03.2022)

2 marked homework assignments (50%)

1 oral exam (50%)

Literature -
Last update: doc. Mgr. Petr Gregor, Ph.D. (30.03.2022)
  • 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

  • Xavier Viennot, The Art of Bijective Combinatorics, online video lectures: http://www.viennot.org/abjc-course.html

  • Torsten Mütze, Combinatorial Gray codes-an updated survey, https://arxiv.org/abs/2202.01280

  • The Combinatorial Object Server Website: http://combos.org

Syllabus -
Last update: doc. Mgr. Petr Gregor, Ph.D. (30.03.2022)
  • Flip graphs
  • Binary strings (binary reflected Gray code)
  • Binary strings (monotone and balanced Gray codes)
  • Combinations (transpositions and shifts)
  • Catalan objects (parenthesis expressions)
  • Middle levels theorem
  • Permutations (transpositions, shifts and reversal)
  • Permutations (linear extensions)
  • Permutations (pattern-avoiding permutations)
  • Geometric objects (triangulations, non-crossing matchings)
  • De Bruijn sequences
  • Spanning trees and bases of matroids

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html