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)