Algorithms and Data Structures II
In the winter semester 2017/2018, 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 Friday from 9:00 in room S3.
Classes (exercises) are on Tuesdays from 12:20 in room S10. They are taught by Petr Kučera. Czech-speaking students can also select any classes of the Czech version of the course, but they are likely to be differences in the order of topics taught.
Syllabus
date | topic |
---|---|
6. 10. | Searching in text: notation on strings, naïve algorithms, the KMP (Knuth, Morris, Pratt) algorithm and its analysis. |
13. 10. | Text searching continued: Aho-Corasick algorithm searching for multiple strings simultaneously. Using rolling hash functions: the Rabin-Karp algorithm. |
20. 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. |
27. 10. | Network flows: An equivalent definition of a flow. Layered networks and blocking flows. The Dinitz's algorithm. |
3. 11. | Network flows: The Goldberg's algorithm (preflow push). |
10. 11. | Network flows: The rest of analysis of Goldberg's algorithm. Introduction to boolean circuits. |
17. 11. | Enjoy the holiday. |
24. 11. | Parallel programming on boolean circuits: binary addition. Comparator networks and bitonic sorting. |
1. 12. | Plan: Geometric algorithms in the plane: convex hull, line segment intersection, Voronoi diagrams, point location and persistent search trees. |
Recommended reading
- Dasgupta, Papadimitriou, Vazirani: Algorithms (a beautiful books on algorithms covering the most of our lecture, available online)
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd or later edition), Mc Graw Hill 2001
- Matoušek, Nešetřil: Invitation to Discrete Mathematics, Oxford University Press. (background in combinatorics and graph theory)
- Other materials in Czech language