# Discrete Models and Algorithms

**Coordinated by:** Department of Applied Mathematics

**Study branch coordinator:** Doc. RNDr. Martin Klazar, Dr.

#### Specializations:

**–**Discrete mathematics and algorithms**–**Geometry and mathematical structures of computer science**–**Optimization

The program offers wide education in theoretical and mathematical fundaments of computer science. Students obtain knowledge in the area of discrete models and related algorithmic and data techniques, and various mathematical methods for their design. The study familiarizes the student both with the last results on discrete models, algorithms and optimization, and with possibilities and limitations in solving related algorithmic questions. The student acquires thorough mathematical knowledge necessary for analysis and design of discrete models and algorithms.

The graduate is familiar with modelling by means of discrete structures, and also with the practical algorithmic aspects. The graduate understands models of computation and their relations and knows limits of effective computing. They have knowledge on algorithmic techniques and data structures, and has awareness of some optimization techniques and results. The graduate familiarized themselves with mathematical approaches to discrete models and algorithms during their studies. This, besides the ubiquitous combinatorics and discrete mathematics, includes geometric, topological, algebraic, number-theoretic, logical, and, last but not least, probabilistic methods. The graduate can asses applicability of these methods to particular discrete model. She or he can follow last research trends in the area. The graduate can work in analyzing and planning of discrete models, and in their algorithmic implementations and in development corresponding technologies. He or she can work in top companies and institutions investigating and developing new technologies, analyzing data or modelling real processes (finances, logistics, economy etc.). He or she is prepared for further Ph.D. study of computer science in domestic institutions or abroad.

#### 1.1 Obligatory Courses

Code | Subject | Credits | Winter | Summer | |

NTIN090 | Introduction to Complexity and Computability | 4 | 2/1 C+Ex | — | |

NTIN066 | Data Structures 1 | 6 | — | 2/2 C+Ex | |

NMAI064 | Mathematical Structures | 5 | — | 2/2 C+Ex | |

NSZZ023 | Diploma Thesis I | 6 | — | 0/4 C | |

NSZZ024 | Diploma Thesis II | 9 | 0/6 C | — | |

NSZZ025 | Diploma Thesis III | 15 | — | 0/10 C |

#### 1.2 Elective Courses - Set 1

The student needs to obtain at least 45 credits for the courses from the following set. The courses NDMI055 and NDMI056 can be attended both by students of Master programs and students of Doctoral programs.

Code | Subject | Credits | Winter | Summer | |

NAIL076 | Logic Programming 1 | 3 | 2/0 Ex | — | |

NDMI010 | Graph Algorithms | 3 | 2/0 Ex | — | |

NDMI013 | Combinatorial and Computational Geometry 2 | 5 | — | 2/2 C+Ex | |

NDMI014 | Topological Methods in Combinatorics | 5 | — | 2/2 C+Ex | |

NDMI015 | Combinatorial Counting | 3 | — | 2/0 Ex | |

NDMI018 | Approximation and Online Algorithms | 5 | — | 2/2 C+Ex | |

NDMI025 | Randomized Algorithms | 5 | — | 2/2 C+Ex | |

NDMI028 | Linear Algebra Applications in Combinatorics | 5 | 2/2 C+Ex | — | |

NDMI036 | Combinatorial Structures | 3 | — | 2/0 Ex | |

NDMI037 | Geometric Representations of Graphs 1 | 3 | 2/0 Ex | — | |

NDMI045 | Analytic and Combinatorial Number Theory | 3 | — | 2/0 Ex | |

NDMI055 | Selected Chapters on Combinatorics 1 | 3 | 2/0 Ex | — | |

NDMI056 | Selected Chapters on Combinatorics 2 | 3 | — | 2/0 Ex | |

NDMI059 | Graph Minors and Tree Decompositions | 3 | 2/0 Ex | — | |

NDMI060 | Coloring of Graphs and Other Combinatorial Structures | 3 | 2/0 Ex | — | |

NDMI064 | Applied Discrete Mathematics | 3 | 2/0 Ex | — | |

NDMI065 | Matroid Theory | 5 | — | 2/2 C+Ex | |

NDMI066 | Algebraic Number Theory and Combinatorics | 3 | 2/0 Ex | — | |

NDMI067 | Flows, Paths and Cuts | 3 | 2/0 Ex | — | |

NDMI074 | Algorithms and Their Implementation | 5 | — | 2/2 C+Ex | |

NDMI087 | Analytic combinatorics | 4 | — | 2/1 Ex | |

NDMI088 | Graph Algorithms 2 | 3 | — | 2/0 Ex | |

NMAG337 | Introduction to Group Theory | 5 | 2/2 C+Ex | — | |

NMAI040 | Introduction to Number Theory | 3 | 2/0 Ex | — | |

NMAI065 | Fundamentals of Category Theory for Computer Scientists | 3 | 2/0 Ex | — | |

NMAI066 | Topological and Algebraic Methods | 3 | — | 2/0 Ex | |

NMAI067 | Logic in Computer Science | 3 | 2/0 Ex | — | |

NMAI071 | Math++ | 5 | — | 2/2 C+Ex | |

NMMA901 | Introduction to Complex Analysis (O) | 5 | 2/2 C+Ex | — | |

NMMA931 | Introduction to Functional Analysis (O) | 8 | 4/2 C+Ex | — | |

NOPT008 | Nonlinear Optimisation Algorithms | 5 | — | 2/2 C+Ex | |

NOPT016 | Integer Programming | 5 | — | 2/2 C+Ex | |

NOPT017 | Multiobjective Optimisation | 3 | — | 2/0 Ex | |

NOPT034 | Mathematical Programming and Polyhedral Combinatorics | 4 | 2/1 C+Ex | — | |

NOPT042 | Constraint Programming | 5 | 2/2 C+Ex | — | |

NOPT051 | Interval Methods | 5 | 2/2 C+Ex | — | |

NTIN017 | Parallel Algorithms | 3 | — | 2/0 Ex | |

NTIN022 | Probabilistic Techniques | 5 | 2/2 C+Ex | — | |

NTIN023 | Dynamic Graph Data Structures | 3 | 2/0 Ex | — | |

NTIN063 | Complexity | 4 | — | 2/1 C+Ex | |

NTIN064 | Computability | 3 | — | 2/0 Ex | |

NTIN067 | Data Structures 2 | 3 | — | 2/0 Ex | |

NTIN100 | Introduction to Information Transmission and Processing | 4 | — | 2/1 C+Ex | |

NTIN103 | Introduction to Parameterized Algorithms | 5 | 2/2 C+Ex | — |

#### 1.3 Elective Courses - Set 2

The student needs to obtain at least 5 credits for the courses from the following set^{1}:

Code | Subject | Credits | Winter | Summer | |

NDMI073 | Combinatorics and Graph Theory 3 | 5 | 2/2 C+Ex | — | |

NOPT018 | Fundamentals of Nonlinear Optimization | 5 | 2/2 C+Ex | — |

^{1}For the two specializations Discrete mathematics and algorithms, and Geometry and mathematical structures of computer science,
we recommend the course
NDMI073; for the specialization Optimization we recommend the course NOPT018. After completing one course from Set 2, the credits are counted for that
set and the minimal credit requirement for Set 2 is satisfied. If the student completes both courses from Set 2, the credits for the second course
are counted among the credits of student's free choice.

#### 1.4 Other Recommended Courses

The list of other recommended courses contains only one course, because of the requirements of the examination area Combinatorial and computational geometry. Additionally, a student can chose other courses from the extensive collection of computer science courses at the Charles University.

Code | Subject | Credits | Winter | Summer | |

NDMI009 | Introduction to Combinatorial and Computational Geometry | 5 | 2/2 C+Ex | — |

#### 1.5 State Final Exam

Each student will get five questions, two from the common background (one from Introduction to complexity and computability and one from Data structures) and three from three examination areas (selected by the student) given in the following lists. At least two of these three examination areas must be selected from student's chosen specialization, one examination area may be selected from another specialization.

#### Examination areas

**1.**Introduction to complexity and computability**2.**Data structures

#### Knowledge requirements

**1. Introduction to complexity and computability**

Models of computation (Turing machines, RAM). Basic complexity classes and their relations.
Approximation algorithms and schemas.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NTIN090 | Introduction to Complexity and Computability | 4 | 2/1 C+Ex | — |

#### Knowledge requirements

**2. Data structures**

Search trees ((a,b)-trees, splay trees). Heaps (regular, binomial). Hashing, collisions,
universal hashing, hash function.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NTIN066 | Data Structures 1 | 6 | — | 2/2 C+Ex |

#### Specialization: *Discrete mathematics and algorithms*

#### Examination areas

**1.**Combinatorics and graph theory**2.**Probabilistic methods and combinatorial enumeration**3.**Polyhedral optimisation**4.**Graph algorithms

#### Knowledge requirements

**1. Combinatorics and graph theory**

Graph colorings and its variants, e.g. choosability. Graph minors, tree width and
its relation to complexity. Geometric representations of graphs (characterization theorems, recognizing
algorithms), algebraic properties of graphs, matching theory. Ramsey theory and Szemeredi's regularity
lemma. Set systems, e.g. Steiner triple systems, finite geometries.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NDMI037 | Geometric Representations of Graphs 1 | 3 | 2/0 Ex | — | |

NDMI059 | Graph Minors and Tree Decompositions | 3 | 2/0 Ex | — | |

NDMI060 | Coloring of Graphs and Other Combinatorial Structures | 3 | 2/0 Ex | — | |

NDMI073 | Combinatorics and Graph Theory 3 | 5 | 2/2 C+Ex | — |

**2. Probabilistic methods and combinatorial enumeration**

Combinatorial counting, generating functions, recurrences, asymptotic estimates of functions.
Basic probabilistic models, linearity of expectation, variance and its uses, Markov's inequality and its
application to particular examples. Chernov's inequality. Lovasz local lemma. Probabilistic constructions
and algorithms.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NDMI015 | Combinatorial Counting | 3 | — | 2/0 Ex | |

NDMI087 | Analytic combinatorics | 4 | — | 2/1 Ex | |

NDMI025 | Randomized Algorithms | 5 | — | 2/2 C+Ex | |

NTIN022 | Probabilistic Techniques | 5 | 2/2 C+Ex | — |

**3. Polyhedral optimization**

Theory of polyhedra, travelling salesman problem, classes of special matrices, integrality,
matchings and flows in networks, matroid theory, ellipsoid method.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NTIN090 | Introduction to Complexity and Computability | 4 | 2/1 C+Ex | — | |

NDMI065 | Matroid Theory | 5 | — | 2/2 C+Ex | |

NOPT034 | Mathematical Programming and Polyhedral Combinatorics | 4 | 2/1 C+Ex | — |

**4. Graph algorithms**

Advanced algorithms for shortest paths, transitive closure, flows in networks, cuts, matchings
and minimal spanning trees, testing of planarity of a graph, drawing a graph in the plane. Graph
data structures: union-find, link/cut trees, E-T trees, fully dynamic maintaining of connectivity
components, common ancestors in trees (LCA).

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NDMI010 | Graph Algorithms | 3 | 2/0 Ex | — | |

NDMI088 | Graph Algorithms 2 | 3 | — | 2/0 Ex | |

NTIN067 | Data Structures 2 | 3 | — | 2/0 Ex |

#### Specialization: *Geometry and mathematical structures in Computer Science*

#### Examination areas

**1.**Combinatorial and computational geometry**2.**Structures in Computer Science**3.**Topology in Computer Science and Combinatorics**4.**Category theory in Computer Science**5.**Number theory in Computer Science

#### Knowledge requirements

**1. Combinatorial and computational geometry**

Basic theorems on convex sets (Helly's theorem, Radon's theorem, Caratheodory's theorem,
hyperplane separation theorem) and their extensions (fractional Helly's theorem, colored
Caratheodory's theorem, Tverberg's theorem), Minkowski's theorem on lattices, incidences of points
and lines, geometric duality, convex polytopes (basic properties, combinatorial complexity),
Voronoi diagrams, convex-independent sets, halving lines, complexity of the lower envelope of
segments.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NDMI009 | Introduction to Combinatorial and Computational Geometry | 5 | 2/2 C+Ex | — | |

NDMI013 | Combinatorial and Computational Geometry 2 | 5 | — | 2/2 C+Ex |

**2. Structures in Computer Science**

Relations and relational structures. Ordered sets. Suprema and infima, semilattices and lattices.
Fixed-point theorems. Distributive lattices. Boolean and Heyting algebras. Basics of universal algebra.
Fundamentals of general topology, topological constructions. Scott's topology, DCPO and domains.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NMAI064 | Mathematical Structures | 5 | — | 2/2 C+Ex | |

NMAI066 | Topological and Algebraic Methods | 3 | — | 2/0 Ex |

**3. Topology in Computer Science and Combinatorics**

Basics of metric and general topology. Topological constructions, special
spaces, compact spaces and connected spaces. Simplicial complexes, simplicial maps.
Jordan curve theorem (informatively, its place in discrete mathematics). The Borsuk–Ulam
theorem and its applications: the sandwich theorem, the necklace theorem, chromatic
number of Kneser graphs. Brouwer's fixed-point theorem.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NMAI064 | Mathematical Structures | 5 | — | 2/2 C+Ex | |

NDMI014 | Topological Methods in Combinatorics | 5 | — | 2/2 C+Ex |

**4. Category theory in Computer Science**

Categories, functors, transformations, examples. Limits and colimits,
special constructions. Adjunction, relation to categorical constructions.
Reflections and coreflections. Examples of adjoint situations.
Cartesian closed categories. Categories and structures, especially
structures used in Computer Science. Monadic algebras.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NMAI065 | Fundamentals of Category Theory for Computer Scientists | 3 | 2/0 Ex | — |

**5. Number theory in Computer Science**

Diophantine approximation (Dirichlet's theorem, Farey fractions, transcendental
numbers). Diophantine equations (Pell's equation, Thue equations, four squares theorem,
Hilbert's tenth problem). Prime numbers (bounds on the prime-counting function,
Dirichlet's theorem). Geometry of numbers (lattices, Minkowski's theorem).
Congruences (quadratic residues). Integer partitions (identities, e.g.,
the pentagonal identity).

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NMAI040 | Introduction to Number Theory | 3 | 2/0 Ex | — |

#### Specialization: *Optimisation*

#### Examination areas

**1.**Nonlinear programming**2.**Discrete optimisation processes**3.**Multiobjective and integer programming**4.**Parametric programming and interval methods

#### Knowledge requirements

**1. Nonlinear programming**

Properties of convex sets and convex functions. Generalizations of convex functions.
Necessary and sufficient optimality conditions for free and constrained extrema
in problems of nonlinear programming. Quadratic programming. Semidefinite programming.
Duality in nonlinear programming. Methods for solving problems with free and constrained extrema,
including penalization and barrier methods. One-dimensional optimization.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NOPT008 | Nonlinear Optimisation Algorithms | 5 | — | 2/2 C+Ex | |

NOPT018 | Fundamentals of Nonlinear Optimization | 5 | 2/2 C+Ex | — |

**2. Discrete optimisation processes**

Algorithmic game theory, election mechanisms, electronic auctions, applications of
submodular functions in economy. Optimization based on enumeration, generating functions
of edge cuts and of perfect matchings, enumerative dualities, the maximum cut problem for
graphs embedded in surfaces.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NDMI064 | Applied Discrete Mathematics | 3 | 2/0 Ex | — | |

NOPT018 | Fundamentals of Nonlinear Optimization | 5 | 2/2 C+Ex | — |

**3. Multiobjective and integer programming**

Various approaches to solving problems with several criteria. Functional associated to
a problem of vector programming. Pareto optimal solution. Problems of linear and
nonlinear vector optimization. Methods for obtaining Pareto optimal solutions.
Problems of linear programming with integrality conditions or with binary variables.
Nonlinear optimization problems with integrality conditions.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NOPT016 | Integer Programming | 5 | — | 2/2 C+Ex | |

NOPT017 | Multiobjective Optimisation | 3 | — | 2/0 Ex |

**4. Parametric programming and interval methods**

Domains of stability of solutions, one-parametric and multi-parametric programming, relation to
multiobjective optimization. Interval linear algebra (systems of linear equations, regularity, eigenvalues).
Linear programming with imprecise data. Deterministic global optimization, lower and upper bounds on
objective function and optimum value.

**Recommended courses**

**Recommended courses**

Code | Subject | Credits | Winter | Summer | |

NOPT017 | Multiobjective Optimisation | 3 | — | 2/0 Ex | |

NOPT051 | Interval Methods | 5 | 2/2 C+Ex | — |