The university of the authors of Submission 71

The course is mandatory for all undergraduate CS students

Recommended in the 3rd semester (after ADS I in the 2nd semester)

** 1. Pattern Matching **

• Algorithm Knuth-Morris-Pratt

• Algorithm Aho-Corasick

• [Algorithm Rabin-Karp]

** 2. Flows in Networks **

• Augmenting path algorithm

• Dinitz algorithm

• Goldberg algorithm

• Matching in a bipartite graph

• Min cost max flow

** 3. Algebraic algorithms **

• Discrete Fourier transform, its motivation and applications

• Algorithm FFT and its implementation by a "butterfly" circuit

• [Related transformations (cosine transformation - JPEG compression)]

** 4. Parallel arithmetic algorithms **

• Sorting networks (either merge-sort or bitonic sort)

• Carry look-ahead binary number addition algorithms

** 5. Geometric algorithms in the plane **

• Convex hull

• Event controlled plane sweep

• [Voronoi diagram and Delaunay triangulation (Fortune algorithm)]

** 6. Problem reducibility and complexity classes **

• Polynomial transformations and decision problem reductions

• Nondeterministic algorithms, classes P and NP

• NP-complexity

** 7. Approximation algorithms **

• Applications of approximation algorithms, relative error

• One of two examples of approximation algorithms (knapsack, bin packing, scheduling,...), upper error bounds

• Approximation scheme: the principle and an example

** 8. Probabilistic algorithms and cryptography **

• Monte Carlo algorithms (Rabin-Miller primality test)

• Public key cryptography (RSA algorithm)