- Garant předmětu:
- 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:
- No time-table has been prepared for this course
- The course is a part of the following study plans: