Algorithms and Data Structures II

In the winter semester 2018/2019, I teach the English version of the basic course on Algorithms and Data Structures II [NTIN061]. It is primarily intended for students of the English study programs, but everybody is welcome.

The lectures are held on every Monday from 10:40 in room S4.

Classes (exercises) are on Mondays from 15:40 in room S11. They are taught by Matej Lieskovský. Czech-speaking students can also select any classes of the Czech version of the course — we will try to keep both versions synchronized.

If you want to contact me and consult anything, you are welcome to visit me in room S322 or to write me an e-mail to mares+ads@kam.mff.cuni.cz.

Syllabus

date topic
1. 10. Searching in text: notation on strings, naïve algorithms, the KMP (Knuth, Morris, Pratt) algorithm and its analysis.
8. 10. Text searching continued: Aho-Corasick algorithm searching for multiple strings simultaneously. Using rolling hash functions: the Rabin-Karp algorithm.
15. 10. Network flows: Basic definitions and theorems on networks and flows. The Ford-Fulkerson algorithm, proof of its correcntess using cuts. Equality of maximum flow and minimum cut. Integer networks and integer flows. Reducing bipartite matching to integer flow.
22. 10. Network flows: An equivalent definition of a flow. Layered networks and blocking flows. The Dinitz's algorithm.
29. 10. Network flows: The Goldberg's algorithm (preflow push) and its analysis. Simulation: uniform path, bottleneck path, maximum height rule (source code).
5. 11. Network flows: Goldberg's algorithm with the highest vertex rule. Multiplication of polynomials. A review of complex numbers.
12. 11. Complex roots of unity. Fast Fourier transform and its inverse. FFT circuits, non-recursive FFT. Remarks on FFT (slides): algebraic interpretation, spectral analysis, signal processing.
19. 11. Parallel programming on boolean circuits: binary addition. Introduction to comparator networks.
26. 11. Comparator networks and bitonic sorting. Decision problems and reductions between them: SAT and 3-SAT.
3. 12. More reductions: independent set, clique, 3,3-SAT, 3D-matching.
10. 12. Complexity classes P and NP, NP-hard and NP-complete problems and their basic properties. Cook's theorem: SAT is NP-complete (proof sketched).
17. 12. Plan: Fighting hard problems. Special cases: independent set in trees, coloring of interval graphs, pseudopolynomial algorithm for knapsack. Approximation algorithms: traveling salesman in a finite metric space (2-approximation), approximation scheme for knapsack.

Recommended reading and other links

This page is maintained by Martin Mareš