Charles Explorer logo

Algorithms and Data Structures 2

Class at Faculty of Mathematics and Physics |


Optional topics in square brackets, the rest is mandatory.

1. Searching in text - Knuth-Morris-Pratt algorithm - Aho-Corasick algorithm - [Rabin-Karp algorithm]

2. Flows in networks - augmenting path algorithm - Dinic's algorithm - Goldberg's algorithm - matching in bipartite graph - [search for maximum flow of minimum price]

3. Algebraic algorithms - discrete Fourier transformation, its motivation and application - the FFT algorithm and its implementation by the "butterfly" - [related transformations (cosine transformation - JPEG compression)]

4. Parallel arithmetic algorithms - sorting networks (implementation of one sorting algorithm - either merge-sort or bitonic-sort) - carry look-ahead algorithm for addition

5. Basic geometric algorithms in a plane - convex hull - the principle of plane sweeping driven by events - [Voronoi diagram and Delaunay triangulation (Fortune's algorithm)]

6. Transferability of problems and classes of time complexity - polynomial transformation and reduction between decision problems - non-deterministic algorithms, Class P and NP - NP-completeness

7. Approximation algorithms - use of approximation algorithms, ratio and relative error - one or two simple examples of approximation algorithms (knapsack, bin-packing, scheduling on parallel machines) including an upper estimate for their ratio (or relative) error - approximation scheme: principle and example

8. Probabilistic algorithms and cryptography - Monte Carlo algorithms (Rabin-Miller's Primality Test) - public key cryptography (RSA algorithm)


Lecture about various types of algorithms and their time complexity (follows NTIN060 Algorithms and data structures 1).