Datasets containing sensitive personal information could serve as invaluable resources to policy-makers, public institutions, and companies. Yet, their analysis or release could jeopardize the privacy of individuals whose data is contained in such datasets. The focus of this course will be on the notion of differential privacy that, beyond strong academic success (2017 Goedel Prize), made it into the production of companies such as Google and Apple.

A course at the boundary between theory and practice, focused on efficient implementation of algorithms on real hardware. Architecture of computers, compilers, and operating systems from the programmer's point of view. Adapting algorithms to concrete machines. Instead of concrete frameworks, we will study the underlying principles.

Free continuation of the lecture NDMI059, now focused on algorithmic consequences (Courcelle's metatheorem, etc.).

This lecture will illustrate various surprising ways to combine the techniques from (mostly complex) analysis with the machinery of (ordinary and exponential) generating functions to solve (almost effortlessly!) some combinatorial counting problems that are too hard for conventional methods. We will assume no prior knowledge of complex analysis whatsoever. Some basic prior familiarity with generating functions is helpful but is not necessary.

This is a follow-up course to NMAG403 Combinatorics. We will see a different construction of Steiner triple systems and we will prove that pairs of orthogonal Latin squares exist for every order n > 6. The main part of the course will be devoted to finite projective spaces. Here the main result says that for dimension greater than 2, the order of a finite projective space is always a power of a prime.

When you get more time or space, can you solve more problems? Can you solve SAT in space n^{1/2} and time n^2? Is it easier to solve SAT if you know that there is at most one solution? How can Alice convince Bob that Coke and Pepsi taste differently? During this course we will address all of these questions and many more. This course will introduce students to many fundamental concepts of computational complexity.

💻 Hands-on Coding Seminar: This seminar focuses on creating educational videos about math, algorithms, and related topics using languages like Motion Canvas or the Python library Manim.

🎬 You will work on a video project, either individually or in a team. By the end of the semester, the goal is for you to have created something comparable to the Summer of Math Exposition videos.

A survey of work of Paul Erdős that laid the foundations of moden discrete mathematics. At a leisurely pace, we shall cover a subset (determined by the students' vote) of the following topics: Erdős's proof of Bertrand's postulate. Erdős's proof of Turán's theorem. Hamilton cycles. Ramsey's theorem and Ramsey numbers. Delta-systems and Deza's proof of an Erdős-Lovász conjecture. Sperner's theorem and the Erdős-Ko-Rado theorem. Van der Waerden's theorem and van der Waerden numbers. Extremal graph theory. The Friendship Theorem, strongly regular graphs, and Moore graphs of diameter two. The Erdős-Rényi random graphs and their evolution. (The course will be based on the book https://www.megabooks.cz/p/17179094/discrete-mathematical-charms-of-paul-erdos .)

The course is an introductory course in complex networks. This topic combines areas of graph theory and combinatorics with the analysis of real-world complex systems. The topics of the course cover some problems from the area of structural graph theory, selected areas of spectral theory, random graphs and the problem of obtaining decompositions of vertices. Lectures are supplemented by seminars having partly theoretical and partly computational forms.

Integer Programming is an optimization tool rich both in theory and applications. Computational Social Choice is a field of growing relevance which considers the computational aspects of elections, fair divison, opinion dynamics, etc. In this course, we will describe parameterized algorithms for important classes of IP, and show their applications to problems from computational social choice.

This is a very active area of research, and this course is at the bleeding edge of what is known, thus presenting fresh research opportunities.

Essentials of information theory, error-correcting codes and communication complexity.

Modern computer science often uses mathematical tools that reach beyond the scope of standard mathematical courses in the bachelor program. This course will present a (somewhat condensed) introduction to several fields of mathematics that proved especially useful in computer science and in discrete mathematics. Computer science applications will be shown as well. This course is suitable for master's or PhD students of computer science.

The contents of the lecture alters (with a period of 3 years). This year we intend to cover: Measure theory (including a little bit of continuous probability), higher-dimensional geometry, and functional analysis.

The language of the lecture will be Czech or English. (It will be English if there is at least one person in the audience who does not understand Czech.)

This is a master-level course focusing on two topics in combinatorial optimization: i) structure of polytopes and the complexity of their description, ii) efficient methods for optimization over polytopes (and polyhedra).

In the first part of the lecture, we will cover basics of the theory of polytopes such as the Minkowski-Weyl theorem, face-lattice, 1-skeleton, etc.

In the second part we describe in detail the ellipsoid algorithm and the interior point methods (IPMs). It is worth mentioning that the framework of IPMs is a key ingredient of the recent algorithm for exact maximum flow in almost linear time.

This course follows the previous one called Fundamentals of Nonlinear Optimization (NOPT018), which discusses the theoretical formulations of a nonlinear optimization problem and its properties. In this course, various classes of optimization algorithms are discussed regarding their efficiency, computational complexity, and several other global properties. The course describes unconstraint and constraint optimization tasks with the nonlinear domain or function. Methods include (quasi)-newton methods, conjugate gradient, interior point, trust-region, etc.

Selected topics from code optimization as implemented in production compilers (primarily GCC and LlVM). There are no formal prerequisites. The course will start with an introduction to intermediate languages, control flow graph and SSA form.

🔭 This (somewhat experimental) lecture explores how probability connects mathematical theory with our understanding of the world - from foundational ideas to practical modeling.

📐 We'll examine mathematical foundations like entropy and its various interpretations and applications, Dutch Book theorems, von Neumann-Morgenstern axioms, relationships with high-dimensional spaces, connections to machine learning, statistics, forecasting, Bayesian inference, and more.

🧭 Instead of focusing deeply on a particular topic, the lectures will explore various ideas that we find insightful, drawing inspiration from information theory, Bayesian statistics, and some LessWrong-inspired aesthetics of modeling and understanding the world through probability.

📚 A basic understanding of probability is assumed (e.g. Probability 1). Fondness of a probabilistic viewpoint is recommended. Some familiarity with related fields will help you get more from the lecture but it is not required.

Use of randomness allows to solve problems more efficiently or even to solve problems that are otherwise intractable. The course covers somewhat advanced techniques for design of randomized algorithms. We cover diverse topics including random walks on graphs, counting, streaming algorithms, PCP theorem.

We assume knowledge on the level of the courses NDMI084 Introduction to approximation and randomized algorithms and NTIN022 Probabilistic Techniques.

Course will be self-contained and no previous knowledge of the area is necessary.

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.

Students present papers on new results in the field of algorithms and data structures.

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.

A sequel to the Seminar on TeX from the winter semester. We will focus on various extensions of TeX (pdfTeX, LuaTeX) and other tools for digital typesetting.

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