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

This page is maintained by Martin Mareš