We cover selected techniques of design and analysis of approximation and online algorithms. We assume knowledge on the level of the Bc. course NDMI084 Introduction to approximation and randomized algorithms. Recommended for Mgr. students.

Course is focusing on advanced algorithms of code optimization used in production quality compilers. The topics can be adjusted according to interests of participants. Usually we focus on the intermediate languages, Single static assignment form, scalar optimization and loop optimization.

The goal of the course freely follows the course Graphs and Networks (NDMI110). We will discuss more extended topics in complex networks in the areas of centralities, random networks, community structure, and more.

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.

This course extends NTIN066 Data Structures I. It covers more advanced techniques of design and analysis of data structures: deterministic representation of static sets, data structures for integers, basic data structures for graphs, dynamic cache-oblivious search trees, dynamization, persistence, succinct data structures, computation in stream model.

At a leisurely pace, we shall cover a subset (chosen by the students) of the following topics: Proof of Bertrand's postulate. Sperner's theorem and the Erdős-Ko-Rado theorem. Turán numbers. Property B and hypergraph colouring. Extremal graph theory. Hamilton cycles. The Friendship Theorem, strongly regular graphs, and Moore graphs of diameter two. Chromatic number of graphs and the probabilistic method. Van der Waerden's theorem and van der Waerden numbers. The Erdős-Szekeres and the Sylvester-Gallai theorems. Delta-systems and Deza's proof of an Erdős-Lovász conjecture. The De Bruijn-Erdős theorem. The Erdős-Rényi random graphs and their evolution. Ramsey's theorem and Ramsey numbers.

This is a follow-up course to GRG 1 from the winter semester, but is also accessible to students who didn't attend GRG 1. Topics cover various algorithmic and structural aspects of graph drawings and geometric intersection representations.

Algorithms for planar embedding in linear time, further results on minimum spanning trees (algorithm with expected linear complexity, Pettie's optimal algorithm), decomposition-based techniques and some data structures.

Further in-depth treatment of the topics introduced in NDMI059 Graph minors and tree decompositions, focusing on giving an outline of the proof Minor Structure Theorem and showcasing some of its applications. We will also cover recent developments towards the Hadwiger's conjecture.

A course in structural graph theory. The first part focuses on graph minors, the second on various graph decompositions. Covers sections 1-4 of the lecture notes.

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 algorithms for important IP and IP-related problems, 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.

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.

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 the period of 3 years). This year we intend to cover topology. Coincidentally, this year, we also run a lecture Topological Methods in Combinatorics (NDMI014) with a partially overlapping contents (and the period of 2 years). Thus we have decided to merge the lectures. If possible, vote for and enroll to NDMI014. (It is not a big difference but it will be easier to handle.)

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.

Introduction to matroid theory. It covers basic notions, representability, graphic matroids, and some algorithmic aspects of matroids.

The class expands on the basic course on computational complexity (NTIN063). It introduces various types of boolean circuits, branching programs and arithmetic circuits. We will show relationship between various circuit classes and traditional complexity classes. We will also show several classical lower bound results on circuit size.

The class is intended for advanced master's students and doctoral students.

Do you want to use a computer to deal with math problems? Do you find Wolfram alpha limited to only basic problems? Do you prefer open source software? Do you prefer Python over "Mathematica language"? Come and learn to use Sage!

We will cover symmetries of graphs and structures in the context of extremal problems and their structural extension properties. Particularly we will discuss the extension property for partial automorphisms (EPPA).

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

In this semester, we will focus on Evolutionary graph theory -- the field which studies random processes that model how entities (such as opinions, viruses, or genetic mutations) propagate through network-structured populations. Along the way we introduce notions such as Markov chains or martingales and we answer questions such as "How long does it take until a randomly typing monkey types a word 'abracadabra'?" We assume basic knowledge of discrete mathematics and probability.

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.

Streaming algorithms are designed for analyzing data in a single pass with a small memory footprint. We will cover sampling and sketching techniques to summarize large amounts of data into a concise summary, typically logarithmic in the data size, that can be used to approximately answer certain queries. While we will primarily focus on the design and formal analysis of streaming algorithms, we will also prove lower bounds on their accuracy and occasionally discuss practical considerations when applying these algorithms.

Partial order, special partial orders in computer science. DCPOs, domains. Continuous and algebraic posets. Introduction to topology.

The aim of the lecture is to provide an introduction to topology and then focus on applications of topology to mostly combinatorial problems, e.g., providing a tight bound on chromatic number of so called Kneser graphs. The central tool for such applications is the Borsuk-Ulam theorem which will be thoroughly explained. This year the lecture will be merged with Mathematics++ which means that the introduction to topology will be slightly deeper.