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.

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 (monotone, hereditary and minor-closed classes, treewidth and structural properties of low-treewidth decompositions),
• extremal graph theory (Szemerédi's regularity lemma, Erdős-Stone-Simonovits theorem, Kővári-Sós-Turán theorem, pseudorandom graphs and Chung-Graham-Wilson theorem, graph limits),
• extremal and Ramsey-type combinatorics (Hales-Jewett theorem and its density version, Gallai-Witt theorem, Roth's theorem).

We will cover some classical topics of extremal theory of finite set systems: theorems of Sperner, Erdos-Ko-Rado, Frankl-Wilson. Applications will include the Littlewood-Offord theorem, Strong and weak saturation of hypergraphs and synchronization of DFA's. If time permits, we will proceed with the Alon's Combinatorial Nullstellensatz and applications thereof.

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.

• 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.

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.

The content of this course are advanced topics in computational complexity. This semester will be devoted to edit distance. Edit distance is a measure of string similarity. It has various applications in bioinformatics, text processing, etc. In this course we will focus on various aspects of edit distance: from algorithms and lower bounds to sketching and error-correction. This will showcase various algorithmic and complexity issues.

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.

🔭 This seminar explores topics in probability and algorithms.

📐 The topics are selected on the fly. Here's a general plan for this semester: We want to dig into the relations of probability with high-dimensional spaces and with some topics related to neural nets (stochastic gradient descent, adversarial attacks, ...).

📚 A basic understanding of probability is assumed (e.g. Probability 1). Fondness of probability is highly recommended. Check out notes from the past seminar (different topics, similar aesthetics). https://bayesbitsbrains.github.io/

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

📝Streaming algorithms are designed to analyze massive datasets in a single pass while using only a small amount of memory. We'll cover sampling and sketching techniques, which compress large streams into concise summaries—often just logarithmic in size—that still allow us to answer queries approximately but efficiently.

🔍We'll begin with foundational problems, including identifying the most frequent items and approximating distributions. Then we'll explore more advanced topics such as sketches for geometric or graph data. We'll also prove lower bounds on sketches' performance and occasionally discuss practical considerations when applying these algorithms. Finally, we'll discuss robustness of sketches to attacks by adaptive adversaries⚔️.

The lecture will partially follow the course on Randomized algorithms (NDMI025), but it is not a prerequisite (we'll recap the necessary background).

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

Seminář věnující se využití současných AI modelů (primárně chatbotů) 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.