Advanced Algorithms

Garant předmětu:

Lecturer:

Tutor:

Supervisor:

Department of Theoretical Computer Science

Synopsis:

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.

Requirements:

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. [2] 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. [5] 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.

Note:

Further information:

https://courses.fit.cvut.cz/MI-PAL/

No time-table has been prepared for this course

The course is a part of the following study plans:

• Master branch Knowledge Engineering, in Czech, 2016-2017 (elective course)
• Master branch Computer Systems and Networks, in Czech, 2016-2019 (elective course)
• Master branch Design and Programming of Embedded Systems, in Czech, 2016-2019 (elective course)
• Master branch Web and Software Engineering, spec. Info. Systems and Management, in Czech, 2016-2019 (elective course)
• Master branch Web and Software Engineering, spec. Software Engineering, in Czech, 2016-2019 (elective course)
• Master branch Web and Software Engineering, spec. Web Engineering, in Czech, 2016-2019 (elective course)
• Master program Informatics, unspecified branch, in Czech, version 2016-2019 (VO)
• Master branch System Programming, spec. System Programming, in Czech, 2016-2019 (elective course)
• Master branch System Programming, spec. Computer Science, in Czech, 2016-2017 (compulsory course of the branch)
• Master branch Knowledge Engineering, in Czech, 2018-2019 (elective course)