The advisors choose accessible open problems from areas that include the design of algorithms, data structures, complexity theory, and more. The students under the guidance of the advisors, try to solve those problems during the semester. We put emphasis on collaborative teamwork and teaching problem-solving skills. Suitable for bachelor or master students.

We will concentrate on advanced topics in code optimization including code generation, register allocation, scheduling, loop optimization etc.

This semester, I have several conferences (I will need to skip approx. 3-4 lectures) and therefore we will partly have a seminar form giving opportunity to present interesting compiler-related projects.

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)

Where do computer science concepts come from, how did they evolve and do we even agree on what they mean? In this course, we will look at concepts such as functions, monads, trees, objects and processes from an interdisciplinary perspective. We will follow the concepts as they change when they cross boundaries between formal definitions, concrete implementations, and intuitive metaphors.

This basic course in nonlinear optimization covers both theoretical fundamentals and applications. We assume a knowledge of linear programming and recommend completing the course Discrete and Continuous Optimization (NOPT046) beforehand. The course is usually held once every two years.

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.

• We will learn to use LEAN to write computer-verifiable proofs of mathematical statements.
• Examples from linear algebra, discrete mathematics, number theory, and analysis.
• Will be held in English if there are non-Czech students interested in it.
• Web is of the last year, this year will be even better :-)

We will show several (sometimes rather unexpected) applications of linear algebraical methods in combinatorics and graph theory. As a sample for tasting: Can you describe all graphs with the property that any two different vertices have exactly one common neighbor?

Games have long served as benchmarks and marked milestones of progress in artificial intelligence (AI). This course teaches you fundamental formalisms, solution concepts and algorithms. We show how to solve both perfect and imperfect information games, and you will understand the deep connections and application of reinforcement learning to game theory. At the end of the course, you will implement algorithms to optimally solve (i.e. converge to Nash Equilibria) in small interesting games - notably small poker variants.

Ever wondered what headlines like "Hackers hacked into XY" actually mean? Ever wondered how an attacker could turn an innocent segfault into full control of your machine? Or leak sensitive data from your application's DB using nothing but a single search field? In this course we will cover some of the many security pitfalls one will eventually fall into when building anything with computers. You will learn the foundations of modern computer security, how attackers think and how to use this offensive mindset to write better, more secure, programs and applications.

Chapters in the life and work of W.T. Tutte in graph theory. (In English.) We focus on topics in which Tutte played a special role (e.g. 1-factors, Hamitonian circuits, chain groups associated with graphs, V-functions, planar enumeration), looking at how Tutte was led to his theorems and the proofs that he gave for them. The course involves reading Tutte's own account of his work in his book Graph Theory as I Have Known It (1998), supplemented where necessary by other sources. Participants will prepare an exposition of one such topic themselves, to be given later in the semester as an informal class presentation and as a subsequent short write-up that may develop the topic in their own direction of interest.

This year, the course provides an introduction to the emerging field of "quantum graph theory", which studies quantum versions of classical graph parameters. In the course, we focus on the notions of quantum homomorphisms, quantum chromatic number, quantum isomorphisms, and quantum automorphism groups of ordinary graphs. In doing so, we hope to give a taste of this exciting new field and how it connects to operator algebras and quantum information. Knowledge of bachelor-level algebra (Algebra 1, Linear Algebra 1+2) and graph theory is assumed. Familiarity with algebraic graph theory, noncommutative algebra, quantum information theory, or functional analysis is a plus, but is not required.

This course is on advanced topics in computational complexity. The current semester will be an introduction to space-bounded computation, through the perspective of computing with full memory. The first half will cover classic results in space complexity, while the second half will focus on the recent catalytic computing model. No prior experience with space or complexity is needed, aside from some familiarity with Turing machines and mathematical maturity.

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.

Theorems of Ramsey type are typically proved in two steps. First, the statement is established for vertex colorings or 0-dimensional spaces — in the case of Ramsey's theorem, this reduces to the classical pigeonhole principle. In the second step, the result is extended to higher dimensions.

While the standard pigeonhole principle is straightforward, its counterparts for other Ramsey-type results are far from trivial. For instance, the Hales–Jewett theorem, which acts as the "pigeonhole" base for the Graham–Rothschild theorem, is a deep mathematical result. This lecture aims to introduce students to the core proof techniques behind these and related theorems.

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.

Presentation of papers and new results from algorithmic game theory, possibly solving problems from this area. Topics may include algorithmic game theory, combinatorial optimisation, mechanism design, fair allocation, market algorithms, network optimisation, computational economics, and related areas of theoretical computer science.

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.

Nedávno se podařilo objevit téměř zapomenutý archiv profesora Housmana, který zachycuje přibližně 25 let studentských projektů REU z kooperativní teorie her. Skrývá množství tvrzení, důkazů, výpočtů a nápadů, z nichž řada nebyla nikdy dále systematicky zpracována.

Na semináři se do tohoto matematického archivu společně vydáme. Budeme rekonstruovat nalezené výsledky, ověřovat jejich platnost, hledat chyby, chybějící předpoklady a protipříklady a zkoušet možná zobecnění. Jednotlivé výsledky se pokusíme propojit a postupně z nich sestavit mapu vztahů a otevřených otázek ukrytých v archivu.

Cílem nebude jen studovat známou teorii, ale zjistit, co se během čtvrtstoletí REU projektů podařilo objevit – a co dalšího se z těchto výsledků můžeme dozvědět.

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

Looking up a new 'thing' in a table of 'known things' is a common task in science. If a molecule is synthesised, we want to know which substance it is or if we actually created something new. But as molecules usually do not answer to the question "Hi, have we met before?" a more systematic approach is required. One option is to structurally represent the molecule by a graph and run a graph isomorphism test against all molecule graphs in a database. But how do those test algorithms actually work? In this course we study three types of algorithms: Specialised efficient algorithms for restricted graph classes, algorithms that are fast in most cases but take exponential time in the worst case, and Babai's famous quasi-polynomial algorithm, which has the lowest known worst-case runtime, but is quite slow in practical application. For a nice introduction to the topic, see: Martin Grohe and Pascal Schweitzer. 2020. The graph isomorphism problem. Commun. ACM 63, 11 (November 2020), 128–134. https://doi.org/10.1145/3372123

Use the power of formal logic to specify programming languages, define type systems and make languages safer. In this course, we will introduce theoretical concepts and tools for studying programming languages, including models based on the lambda calculus, operational semantics, and concepts related to type systems such as type safety. The course will cover all you need to study advanced topics in programming language theory and their practical applications.

Seminář věnující se využití současných AI modelů (primárně LLM) v pracovním procesu. Seminář se bude věnovat hlavně následujícím dvěma problematikám: Využití AI v programování a při práci s informacemi.