Algorithm and Data Structure II course (syllabus)

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)