Selected Combinatorics Applications
- Garant předmětu:
- Tomáš Valla
- Dušan Knop, Šimon Schierreich, Ondřej Suchý, Tomáš Valla
- Dušan Knop, Michal Opler, Jan Pokorný, Šimon Schierreich, Ondřej Suchý, Tomáš Valla
- Department of Theoretical Computer Science
The course aims to introduce students in an accessible form to various branches of theoretical
computer science and combinatorics. In contrast to the basic courses, we approach the issue from
applications to theory. Together, we will first refresh the basic knowledge needed to design and
analyze algorithms and introduce some basic data structures. Furthermore, with the active
participation of students, we will focus on solving popular and easily formulated problems from
various areas of (not only theoretical) informatics. Areas from which we will select problems to be
solved will include, for example, graph theory, combinatorial and algorithmic game theory,
approximation algorithms, optimization and more. Students will also try to implement solutions to
the studied problems with a special focus on the effective use of existing tools.
We assume that the student masters the knowledge acquired in the subjects Discrete Mathematics
and Logic (BI-DML) and Programming and Algorithmization 1 (BI-PA1).
- Syllabus of lectures:
1. Problems of cloakrooms and watermen
Despite the problem of the locker room and the problem of watermen, we will appropriately
establish and further expand some selected knowledge from the basic BI-DML course. We
will continue to use this knowledge in the rest of the course. Evidence will also be an
important concept for the rest of the course, so we will show examples of some evidence
that looks seemingly correct but doesn't really work.
2. Numerical problems
We will deal with interesting problems in discrete mathematics, such as the breakfast
problem, CSP, Sperner's lemma and its applications, the Hercules and Hydra problem and
3. Graph problems
We will imagine problems that can be solved using graph theory, but creating a graph model
may seem unintuitive for these problems. Examples of such a problem are vessel metering,
tunnel passage reconstruction and much more.
4. Geometry and graphing
The aim of the lesson is to acquaint students with the basic problems of computational
geometry, which bring with them many problems in the form of working with real numbers.
We will show how similar problems can be solved and we will get acquainted with why it is
interesting to be able to draw a graph nicely.
5. Solving marital problems
The stable marriage problem is a fundamental problem in pairing theory. The task is to find
among equally large groups of (heterosexual) men and women an assignment to marriage
that is as close as possible to their preferences, so no couple will tend to leave the marriage.
The mentioned problem has many generalizations, either in the form of a stable roommate
problem or in games dedicated to the formation of coalitions. L. S. Shapley and A. E. Roth
were even awarded the Nobel Prize for their work in this field.
6. One to two player games
Let's look at simple combinatorial games such as Nim, Toads and Frogs, Tic-Tac-Toe. We will
generalize these simple games and show some selected features of more complex games,
such as chess, Shannon's number, Go, Game of Life, Poker.
7. Slicing a cake
During the lesson, the basic problems of the theory of fair division will be introduced. It
deals with the fair division of a farm between players and finds many applications in real
world problems. The issue will be illustrated by the example of the cake-cutting problem
8. Inaccurate solutions to difficult tasks
Using the example of the secretary selection problem, we will show how to solve problems
that are considered algorithmically unsolvable under the assumption of the P! = NP
hypothesis for large instances. We will show how to find a solution for similar tasks that is
not the best possible, but in the worst case it differs from the best result by a previously
known constant factor. Another solution to similar unsolvable problems is to create
algorithms such as Monte-Carlo, Las Vegas and others.
9. Online algorithms
For most of the introduced algorithms, we know the entire input at the beginning of the
calculation. In many practical tasks, however, we receive input information gradually and we
must respond flexibly to changes or additional input information. During the lesson, we will
use the example of the sorting and secretary problem to show how such algorithms work,
how to design and use them. Last but not least, we will discuss whether there is an online
counterpart for each off-line algorithm, and explain what a competitive online algorithm
10. Problems suitable for general solvers – SAT
To acquaint students with the problem of satisfiability and its variants. SAT is a prominent
problem of all informatics, which is, among other things, the basis of the whole complexity
theory. On the one hand, from a theoretical point of view, this is an unsolvable problem for
larger instances, but on the other hand, there are many very good optimized commercial
and open-source solvers that can calculate many tasks very quickly. Therefore, students will
practice how to reduce some computational problems to the problem of satisfiability and
thus obtain a relatively efficient algorithm without the need to devise and implement a
complex algorithm. The student will also learn how reducibility is related to the problem
belonging to the NP complexity class.
11. Problems suitable for general solvers - LP and ILP
To acquaint students with the theory of linear programming and its integer variant.
Furthermore, students will practice how to express some computational problems as (integer) linear programs. We will then solve the problems expressed in this way in some
freely available LP solver. The student will also learn how reducibility is related to the
problem belonging to the NP complexity class.
12. Alternative computational models
In addition to the standard RAM computational model, calculations can be performed on
other computational models. A nice example can be, for example, comparator networks or a
tile model. The aim of the lesson is therefore to present these calculation models and show
their (limited) power.
13. (reserve) Parallel algorithms
Modern processors often have not only a single core, but multiple cores. Machines
consisting of many interconnected processors can also be used to perform more complex
calculations. We will introduce a parallel computational model PRAM and its variants. We
will try to solve some known problems significantly faster than sequential calculation, ie
typically in polylogarithmic and constant time.
- Syllabus of tutorials:
1. Problems of hatcheck ladies and watermen
2. Number problems
3. Graph problems
4. Geometry and graph drawing
5. Solving stable marriages
6. Games for one or two players
7. Cake cutting
8. Imprecise solving of intractable problems
9. On-line algorithms
10. Problems for general solvers - SAT
11. Problems for general solvers - LP and ILP
12. Alternative computational models
13. Parallel algorithms
- Study Objective:
The aim of the course is to introduce students to a wide range of topics that theoretical computer
science deals with, and to motivate him to study this field.
- Study materials:
AIGNER, Martin and Günter M. ZIEGLER. Proofs from the book. 4th ed. Berlin: Springer, 2010. ISBN
BERLEKAMP, Elwyn R., John H. CONWAY and Richard K. GUY. Winning ways, for your mathematical
plays. New York: Academic Press, 1982. ISBN 978-0-120-91150-9.
BRANDT, Felix, Vincent CONITZER, Ulle ENDRISS, Jérôme LANG and Ariel D. PROCACCIA. Handbook of
computational social choice. New York: Cambridge University Press, 2016. ISBN 978-1-107-06043-2.
CORMEN, Thomas H., Charles E. LEISERSON, Ronald L. RIVEST and Clifford STEIN. Introduction to
Algorithms. 3rd ed. Cambridge: The MIT Press, 2009. ISBN 978-0-262-03384-8.
MAREŠ, Martin and Tomáš VALLA. Algorithm maze guide. In Prague: CZ.NIC, 2017. ISBN: 978-80-
MATOUSEK, Jiri. Linear Programming: An Introduction to Computer Science [online]. Praha: ITI,
2006. Available from: https://iti.mff.cuni.cz/series/2006/311.pdf.
MATOUŠEK, Jiří and Jaroslav NEŠETŘIL. Chapters in discrete mathematics. 4., ed. published in
Prague: Karolinum, 2009. ISBN 978-80-246-1740-4.
STEWART, Ian. How to slice a cake and other math mysteries. Prague: Argo, Dokořán, 2009. ISBN
- Further information:
- Time-table for winter semester 2023/2024:
- Time-table is not available yet
- Time-table for summer semester 2023/2024:
- Time-table is not available yet
- The course is a part of the following study plans:
- Bachelor branch Security and Information Technology, in English, 2015-2020 (elective course)
- Bachelor branch Web and Software Engineering, spec. Software Engineering, in English, 2015-2020 (elective course)
- Bachelor branch Computer Science, in English, 2015-2020 (elective course)
- Bachelor specialization, Computer Engineering, 2021 (elective course)
- Bachelor specialization, Information Security, 2021 (elective course)
- Bachelor specialization, Software Engineering, 2021 (elective course)
- Bachelor specialization, Computer Science, 2021 (elective course)
- Bachelor specialization, Computer Networks and Internet, 2021 (elective course)
- Bachelor specialization Computer Systems and Virtualization, 2021 (elective course)
- Study plan for Ukrainian refugees (elective course)
- Bachelor branch Computer Science, in English, 2015-2020 original version (elective course)