Hypercube structures - NTIN097
Title: Struktury v hyperkrychlích
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information: http://ktiml.mff.cuni.cz/~gregor/hypercube/hypercube-course.htm
Guarantor: doc. Mgr. Petr Gregor, Ph.D.
Teacher(s): doc. Mgr. Petr Gregor, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Theoretical Computer Science
Opinion survey results   Examination dates   WS schedule   Noticeboard   
Annotation -
Many objects in various areas of theoretical computer science may be formulated as problems in hypercubes. The lecture offers an overview of selected problems studied in hypercubes with emphasis on applications in theoretical computer science. It assumes only elementary knowledge and it is suitable for students in the M.Sc. programme.
Last update: Hric Jan, RNDr. (26.04.2019)
Aim of the course -

The course gives an introduction into the area of hypercube problems.

Last update: T_KTI (28.04.2015)
Course completion requirements -

The course is finished by an exam.

Last update: Gregor Petr, doc. Mgr., Ph.D. (22.09.2020)
Literature -
  • B. Bollobás, Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability, Cambridge University Press, Cambridge, 1986.
  • R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, 2011.
  • S. Jukna, Extremal Combinatorics with Applications in Computer Science, Springer, Berlin, 2001.
  • F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, 1992.
  • selected journal papers.

Last update: T_KTI (28.04.2015)
Requirements to the exam -

The exam consists of solving three sets of exercises during the semester and an oral exam. Average exercise grade will cover 60% of the final mark, and the other 40% will be given for the oral exam.

Last update: Gregor Petr, doc. Mgr., Ph.D. (29.09.2022)
Syllabus -
  • Hypercube characterizations, basic properties.
  • Orbit and stabilizer theorem, group of automorphisms.
  • Parcial cubes, median graphs, convex expansion.
  • Nonexpansive maps, correspondence to 2-SAT.
  • Matchings, Gray codes, Hamiltonian decomposition.
  • Independent spanning trees, robustness of communication.
  • Shadows, intersecting systems, isoperimetric problems.
  • Linear layout problems, width parameters.
  • Influence of variables of boolean functions, harmonic analysis.
  • Packing and covering, applications of self-correcting codes.
  • Turán numbers and other extremal problems.

Last update: T_KTI (28.04.2015)