Selected Combinatorics Applications

Course guarantor:

Michal Opler

Lecturer:

Dušan Knop, Šimon Schierreich, Ondřej Suchý, Tomáš Valla

Tutor:

Dušan Knop, Michal Opler, Jan Pokorný, Šimon Schierreich, Ondřej Suchý, Tomáš Valla

Supervisor:

Department of Theoretical Computer Science

Synopsis:

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.

Requirements:

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

the like.

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

means.

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

978-3-642-00855-9.

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-

88168-22-5.

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

978-80-7363-187-1.

Note:

Further information:

https://courses.fit.cvut.cz/BIE-VAK.21

Time-table for winter semester 2024/2025:

Time-table is not available yet

Time-table for summer semester 2024/2025:

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)
• Bachelor Specialization, Computer Engineering, Version 2024 (elective course)