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

CodeSubjectCreditsWinterSummer
NTIN090Introduction to Complexity and Computability 42/1 C+Ex
NTIN066Data Structures 1 62/2 C+Ex
NMAI064Mathematical Structures 52/2 C+Ex
NSZZ023Diploma Thesis I 60/4 C
NSZZ024Diploma Thesis II 90/6 C
NSZZ025Diploma Thesis III 150/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.

CodeSubjectCreditsWinterSummer
NAIL076Logic Programming 1 32/0 Ex
NDMI010Graph Algorithms 32/0 Ex
NDMI013Combinatorial and Computational Geometry 2 52/2 C+Ex
NDMI014Topological Methods in Combinatorics 52/2 C+Ex
NDMI015Combinatorial Counting 32/0 Ex
NDMI018Approximation and Online Algorithms 52/2 C+Ex
NDMI025Randomized Algorithms 52/2 C+Ex
NDMI028Linear Algebra Applications in Combinatorics 52/2 C+Ex
NDMI036Combinatorial Structures 32/0 Ex
NDMI037Geometric Representations of Graphs 1 32/0 Ex
NDMI045Analytic and Combinatorial Number Theory 32/0 Ex
NDMI055Selected Chapters on Combinatorics 1 32/0 Ex
NDMI056Selected Chapters on Combinatorics 2 32/0 Ex
NDMI059Graph Minors and Tree Decompositions 32/0 Ex
NDMI060Coloring of Graphs and Other Combinatorial Structures 32/0 Ex
NDMI064Applied Discrete Mathematics 32/0 Ex
NDMI065Matroid Theory 52/2 C+Ex
NDMI066Algebraic Number Theory and Combinatorics 32/0 Ex
NDMI067Flows, Paths and Cuts 32/0 Ex
NDMI074Algorithms and Their Implementation 52/2 C+Ex
NDMI087Analytic combinatorics 42/1 Ex
NDMI088Graph Algorithms 2 32/0 Ex
NMAG337Introduction to Group Theory 52/2 C+Ex
NMAI040Introduction to Number Theory 32/0 Ex
NMAI065Fundamentals of Category Theory for Computer Scientists 32/0 Ex
NMAI066Topological and Algebraic Methods 32/0 Ex
NMAI067Logic in Computer Science 32/0 Ex
NMAI071Math++ 52/2 C+Ex
NMMA901Introduction to Complex Analysis (O) 52/2 C+Ex
NMMA931Introduction to Functional Analysis (O) 84/2 C+Ex
NOPT008Nonlinear Optimisation Algorithms 52/2 C+Ex
NOPT016Integer Programming 52/2 C+Ex
NOPT017Multiobjective Optimisation 32/0 Ex
NOPT034Mathematical Programming and Polyhedral Combinatorics 42/1 C+Ex
NOPT042Constraint Programming 52/2 C+Ex
NOPT051Interval Methods 52/2 C+Ex
NTIN017Parallel Algorithms 32/0 Ex
NTIN022Probabilistic Techniques 52/2 C+Ex
NTIN023Dynamic Graph Data Structures 32/0 Ex
NTIN063Complexity 42/1 C+Ex
NTIN064Computability 32/0 Ex
NTIN067Data Structures 2 32/0 Ex
NTIN100Introduction to Information Transmission and Processing 42/1 C+Ex
NTIN103Introduction to Parameterized Algorithms 52/2 C+Ex

1.3 Elective Courses - Set 2

The student needs to obtain at least 5 credits for the courses from the following set1:

CodeSubjectCreditsWinterSummer
NDMI073Combinatorics and Graph Theory 3 52/2 C+Ex
NOPT018Fundamentals of Nonlinear Optimization 52/2 C+Ex

1For 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.

CodeSubjectCreditsWinterSummer
NDMI009Introduction to Combinatorial and Computational Geometry 52/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

CodeSubjectCreditsWinterSummer
NTIN090Introduction to Complexity and Computability 42/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

CodeSubjectCreditsWinterSummer
NTIN066Data Structures 1 62/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

CodeSubjectCreditsWinterSummer
NDMI037Geometric Representations of Graphs 1 32/0 Ex
NDMI059Graph Minors and Tree Decompositions 32/0 Ex
NDMI060Coloring of Graphs and Other Combinatorial Structures 32/0 Ex
NDMI073Combinatorics and Graph Theory 3 52/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

CodeSubjectCreditsWinterSummer
NDMI015Combinatorial Counting 32/0 Ex
NDMI087Analytic combinatorics 42/1 Ex
NDMI025Randomized Algorithms 52/2 C+Ex
NTIN022Probabilistic Techniques 52/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

CodeSubjectCreditsWinterSummer
NTIN090Introduction to Complexity and Computability 42/1 C+Ex
NDMI065Matroid Theory 52/2 C+Ex
NOPT034Mathematical Programming and Polyhedral Combinatorics 42/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

CodeSubjectCreditsWinterSummer
NDMI010Graph Algorithms 32/0 Ex
NDMI088Graph Algorithms 2 32/0 Ex
NTIN067Data Structures 2 32/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

CodeSubjectCreditsWinterSummer
NDMI009Introduction to Combinatorial and Computational Geometry 52/2 C+Ex
NDMI013Combinatorial and Computational Geometry 2 52/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

CodeSubjectCreditsWinterSummer
NMAI064Mathematical Structures 52/2 C+Ex
NMAI066Topological and Algebraic Methods 32/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

CodeSubjectCreditsWinterSummer
NMAI064Mathematical Structures 52/2 C+Ex
NDMI014Topological Methods in Combinatorics 52/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

CodeSubjectCreditsWinterSummer
NMAI065Fundamentals of Category Theory for Computer Scientists 32/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

CodeSubjectCreditsWinterSummer
NMAI040Introduction to Number Theory 32/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

CodeSubjectCreditsWinterSummer
NOPT008Nonlinear Optimisation Algorithms 52/2 C+Ex
NOPT018Fundamentals of Nonlinear Optimization 52/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

CodeSubjectCreditsWinterSummer
NDMI064Applied Discrete Mathematics 32/0 Ex
NOPT018Fundamentals of Nonlinear Optimization 52/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

CodeSubjectCreditsWinterSummer
NOPT016Integer Programming 52/2 C+Ex
NOPT017Multiobjective Optimisation 32/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

CodeSubjectCreditsWinterSummer
NOPT017Multiobjective Optimisation 32/0 Ex
NOPT051Interval Methods 52/2 C+Ex