- Luděk Kučera (guarantor)
- Tomáš Valla
- Department of Theoretical Computer Science
The students will learn the most important advanced algorithms in different domains of the computer science that are not covered by modules of the Bachelor program Informatics and other modules of the Master program. They will also learn how to cope with problems that, according to the present knowledge, are not solvable optimally in polynomially bounded time.
- Syllabus of lectures:
1. Advanced algorithms for network flows.
2. Matching: bipartite and general, minimum cost matching, parallel randomized algorithm.
3. Planar graphs: planarity conditions, planarity testing, isomorphism of planar graphs.
4. Digital signal processing: FFT and spectral compression.
5. Geometric algorithms: convex hull, Voronoi diagram, and others.
6. Streaming algorithms.
7. Primality: randomized a deterministic testing, proof of primality.
8. Approximation algorithms.
9. Approximation schemes.
10. Online algorithms.
11. General heuristic methods: simulated annealing, tabu search, genetic algorithms.
12. Specialized heuristic methods: spectral heuristics, TSP.
13. Randomized algorithms and probabilistic analysis of algorithms.
- Syllabus of tutorials:
1.  Inefficiency/non-termination of the FF algorithm, hecking of the parallel matching algorithm, special cases of matchings.
2. Kuratowski theorem as a planarity testing algorithm, non-planarity of K5 and K33, planar drawing of low-connected graphs, randomized proof of non-isomorphism.
3. Fourier images of fundamental functions, convolution and FT, cosine transformation.
4. Aplications of a convex hull and Voronoi diagram and their relation.
5. Basic examples of streaming algorithms.
6. Aproximation of a robber's problem and the bin-packing.
7. Fundamentals of the spectral graph theory.
8. Examples of the probabilistic analysis of simple heuristics.
9.  Student reports on experimental investigation of implemented algorithms.
- Study Objective:
The goal is to give a list of the most important algorithms in different domains of computer science, to use them to illustrate general principles of the design of effective algorithms, and to show methods to cope with problems that, according to the present knowledge, are not solvable optimally in polynomially bounded time.
- Study materials:
1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. ''Introduction to Algorithms (3d Edition)''. The MIT Press, 2009. ISBN 0262033844.
2. Kleinberg, J., Tardos, E. ''Algorithm Design''. Addison Wesley, 2005. ISBN 0321295358.
- Further information:
- Time-table for winter semester 2019/2020:
- Time-table is not available yet
- Time-table for summer semester 2019/2020:
- The course is a part of the following study plans:
- Knowledge Engineering, in Czech, Presented in Czech, Version 2016 and and 2017 (elective course)
- Computer Systems and Networks, Presented in Czech, Version 2016 to 2019 (elective course)
- Design and Programming of Embedded Systems, in Czech, Version 2016 to 2019 (elective course)
- Specialization Web and Software Engineering, in Czech, Version 2016 to 2019 (elective course)
- Specialization Software Engineering, in Czech, Version 2016 to 2019 (elective course)
- Specialization Web Engineering, Presented in Czech, Version 2016 to 2019 (elective course)
- Master Informatics, Presented in Czech, Version 2016 to 2019 (VO)
- Specialization System Programming, Presented in Czech, Version 2016 to 2019 (elective course)
- Specialization Computer Science, Presented in Czech, Version 2016-2017 (compulsory course of the branch)
- Knowledge Engineering, in Czech, Presented in Czech, Version 2018 to 2019 (elective course)