Second part of lecture on compilers. We will discuss loop optimization, inter-procedural optimization and code generation.

A systematic introduction to the graph coloring theory, including some of the recent developments.

• Critical graphs (their density and application in testing the chromatic number of graphs on surfaces, potential method)
• Discharging method (and an outline of the proof of the Four Color Theorem).
• Variants of graph coloring (fractional, circular, ...), connection to nowhere-zero flows.
• Applications of probabilistic and counting methods.

An advanced course in graph theory and combinatorics. Includes topics from:

• structural graph theory (properties of graph classes defined by forbidden minors, detailed introduction to treewidth from the structural perspective, Erdős-Pósa theorem, Nash-Williams theorem on spanning trees, VC dimension)
• extremal graph theory and additive combinatorics (regularity lemma and its applications)
• polynomial method (in list coloring and graph regularization)

Cílem semináře je dát dohromady studenty a vyučující, kteří mají zájem o kooperativní teorii her. Slouží především jako platforma pro vznik nových témat a formulaci zajímavých problémů, které následně diskutujeme a řešíme. Seminář je směřovaný tím, co jeho účastníky baví a zajímá. Chceme vybudovat kolektiv a propojit mezi sebou lidi, kteří mohou spolupracovat i nad rámec samotného semináře. Studenti si mohou také prostřednictvím semináře vyzkoušet, co obnáší výzkum v matematice, otestovat své schopnosti a na základě této zkušenosti na seminář i navázat prostřednictvím bakalářské/magisterské práce.

Algorithms for different types of flows and cuts, as well as their interrelations, have proven to be invaluable tools for addressing a wide range of graph-related problems (e.g., graph drawing, VLSI design, routing in networks, to name a few). In this course, we will

• describe the main results concerning (multicommodity) flows and cuts in graphs, and on the way we will also

• illustrate various techniques employed in the development of approximation algorithms, such as LP relaxation, probabilistic methods, geometric approaches, SDP relaxation and a greedy approach.

Special graph classes, in this course mainly defined as intersection graphs of geometrical objects in the plane, are intensively studied both for their applied motivation and interesting algorithmic properties. We will see interval graphs, chordal graphs, comparability graphs, and others, their structural characterizations, recognition algorithms as well as algorithms for basic optimization problems that run in polynomial time on graphs from these classes.

The lecture covers advanced algorithms for shortest paths, network flows, minimum spanning trees, and some other graph problems. Several graph data structures will be mentioned, too. Knowledge of Bachelor-level Algorithms and Data Structures 1+2 is assumed.

Parameterized algorithmics analyzes the runtime in finer detail than classical complexity theory: instead of expressing the runtime as a function of the input size only, the dependence on a parameter of the input is taken into account. The aim is to isolate any fast growth of the runtime to a parameter, while the remaining growth of the time is kept low. Apart from giving a deeper theoretical understanding of the complexity of a problem, this can also lead to efficient (practical) algorithms if the parameter describes a property of the inputs, for which the parameter is typically small.

See also video trailer.

Cílem semináře je otestovat možnosti a hranice práce s ChatGPT a do příštích let položit základy pro výuku "plnokrevné" přednášky na toto téma. Studenti mají příležitost se kromě osvojení tohoto nástroje aktivně podílet na obsahu semináře a směru, kterým se bude (především ve své druhé polovině) odvíjet.

Z důvodu povahy předmětu je kapacita omezena.

This year we will focus on Ramsey theory. There are no prerequirements for this course.

A series of lectures on advanced data structures, which extends Master-level Data structures 1 and 2. You can take this course repeatedly, we tackle different topics each year.

Training for programming competitions, especially International Collegiate Programming Contest (ICPC). Practice contests and tutorials on important techniques and problem types. Held once every two weeks for 3 hours.

The students will collaborate on solving open combinatorial problems, which are easily formulated and do not require deep background knowledge. We attempt to choose problems of medium difficulty.

Seminar on Combinatorics is a seminar for students interested in combinatorics. The assumed knowledge corresponds to the first year lectures (Discrete Mathematics and Combinatorics and Graphs I). Therefore, the seminar is especially suitable for students of the 2nd year of Bachelor's studies and older but interested students of the first year are also very welcome.

Main contents of the seminar is that the students present papers on Combinatorics. This means that you will learn something new as well as you will train how to explain some ideas to other students.

Seminar covers several subtopics in Combinatrics including (but not limited to): Combinatorial structures, graph theory, combinatorial geometry, probability, game theory, etc.

Participants of the seminar are invited to the Spring school of Combinatorics.

Also known as the pizza seminar. Come enjoy a slice of pizza and a talk on current topics in theoretical computer science.

Imagine a true statement about finite objects, how can a formal proof of such a statement look? Can it be short? This semester's topic will be about basic propositional proof systems studied in proof complexity (namely Resolution, Frege system, and some algebraic and geometric systems). During the seminars, which will be as interactive as possible, we will work on various exercises which will guide us through the feel of proving something in those proof systems. We will also focus on studying classic lower bounds for those systems. In the later parts of the semester, the students will be free to pick a topic to present, but active participation will be enough to obtain the credit (zápočet). No prior knowledge is assumed, everything is to be explained on the seminar.