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 (Courcell's metathm, 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. I will assume no prior knowledge of complex analysis whatsoever. Some basic prior familiarity with generating functions will be helpful but is not necessary.

We focus on advanced algorithms used by production quality compilers (SSA form, scalar optimizaction, inter-procedural optimization and other topics). We discuss their practical application within open-source compilers (GCC, LLVM and others). This course is not aiming to be comprehensive description of the whole back-end, but we will focus on selected areas and discuss them in greater detail.

The purpose of the lecture is to present several more advanced topics in combinatorial and computational geometry. The individual topics slightly vary each run. This year we intend to cover: Convex independent sets, halving lines, lower envelopes, Tverberg theorem. Probably also: Shellability of polytopes and upper bound theorem.

Přednáška se jen mírně překrývá s Kombinatorikou NMAG403. Zde si ukážeme jinou konstrukci Steinerových systémů trojic, dokážeme, že alespoň 2 ortogonální Latinské čtverce exitují pro každý řád kromě 6. Podstatná část přednášky bude věnována teorii konečných projektivních prostorů, kde hlavním výsledkem bude důkaz, že pro dimenzi větší než 2 je řád konečného projektivního prostoru nutně mocnina prvočísla.

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.

This will be the latest edition of a course that was hugely popular in Montreal between 2007 and 2009. Its enchanting textbook covers a number of topics listed at https://kam.mff.cuni.cz/~chvatal/NDMI107 . This is more material than can be studied in one semester; traditionally, I let the students choose in the beginning its subset that they want me to cover.

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.

An introductory course ranging from theoretical foundations to commonly used cryptographical protocols (e.g., TLS and DNSSEC) and practical computer security.

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

The aim of course is to introduce the main principles of various exact optimization methods based on linear programming and combinatorial optimization with emphasis on large-scale instances. Moreover, during the accompanying tutorial you will gain experience in applying these methods in practice.

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 period of 3 years). This year we intend to cover: Discrete Fourier transform, Representation theory, and Polynomials in many variables

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.

This class is a continuation of Probabilistic Techniques NTIN022. (The knowledge of techniques from that class is necessary to follow this one.) The class is complementing (but not overlapping) with Probabilistic algorithms NDMI025.

We will cover, among others: concentration inequalities, random regular graphs, quasirandomness.

See our video presentation.

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.

We will concentrate on colorings, dimensions, Ramsey theory and sparsity.

Training for programming contests. Held once every two weeks.

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

Team collaboration on solving open combinatorial problems. Easily formulated combinatorial problems of medium difficulty are discussed.

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.