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.
|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.|
- 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