Syllabus
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)
Annotation
Lecture about various types of algorithms and their time complexity (follows NTIN060 Algorithms and data structures 1).