Folowup course for NOPT021 - modern algorithmic game theory

This course is a continuation of NMAI062 Algebra 1, with a focus on foundational results in group and ring theory. We first discuss the isomorphism theorems and their application. The second chapter concerns results on field extensions, algebraic/transcendental numbers, and the classification of finite fields. We then apply the developed theory to discuss algorithmic problems over polynomial rings (fast multiplication/division/factorization). If any time is left, we talk about other algebraic structures of importance in computer science (such as lattices and Boolean algebras).

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.

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.

Join an intensive course in Cooperative Game Theory, taught in English by Michel Grabisch (ERA Chair, AGATE). The course combines solid theoretical foundations with practical applications in voting games, fair allocation, bargaining, and SHAP methods in AI. Classes take place twice a week, from February 17 to March 31. Ideal for students and researchers interested in game theory, economics, operations research, and machine learning.

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.

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

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.

In-depth development of the theory of graph minors, building upon the foundation established in NDMI059 Graph minors and tree decompositions. The focus of the lecture will be on the celebrated Minor Structure Theorem, one of the most fundamental results in the structural graph theory. We will explore the most important ideas that go into the proof of this theorem and showcase some of its applications. We will also cover recent developments towards 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 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 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.

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

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.

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

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.