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. | Plan: Network flows: An equivalent definition of a flow. Layered networks and blocking flows. The Dinitz's algorithm. |
Recommended reading and other links
- 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)
- Last year's lecture
- Other materials in Czech language