The modul covers fundamental and classical results in the area of advanced algorithms. Specifically, the course focuses on basic algorithm design and analysis principles. It addresses greedy approaches, divide and conquer, dynamic programming, randomization and amortization. These techniques are applied to develop solutions to cornerstone algorithmic problems.
Divide and Conquer: Introduction: deterministic Quicksort. Geometric divide and conquer: closest pair problem; line segment intersection; Voronoi diagrams. Fast Fourier Transform (FFT).
Randomized Algorithms: Las Vegas and Monte Carlo algorithms. Randomized Quicksort. Randomized primality test with applications to public-key cryptosystems. Verifying matrix multiplication.
Data Structures: Treaps – randomized search trees. Suffix trees.
Amortized Analysis: Dynamic tables. Fibonacci heaps.
Greedy Algorithms: Introduction. Interval scheduling. Scheduling to minimize lateness. Shortest paths in a graph.
Dynamic Programming: Introduction: weighted interval scheduling. Matrix-chain multiplication. Construction of optimal search trees. Segmented least squares. Subset sums and knapsacks.
Graph Algorithms: Computation of minimum cuts. Maximum-flow problem.
Further Topics: Median Computation. The probabilistic method.