I teach Algorithms and Data Structures II (NTIN061) every Monday at 14:00 in S9 (Malá strana).
If you want to talk to me, send me an email at koutecky+ads2@iuuk.mff.cuni.cz and/or include the text [ADS2] in the email subject, or message me on discord etc. We will then figure out a time and place (physical, zoom, etc.) to meet.
Practice: the ADS2 Arcade has small games for most algorithms of the lecture (failure function sprint, Aho-Corasick, Rolling hash, augmenting paths, push-relabel, sorting networks, FFT, reductions, …). Notation follows the ALG book.
| data | what was taught [resources] |
|---|---|
| 28. 9. | No lecture: St. Wenceslas Day |
| 5. 10. | A few words about AI (slides). String searching: Knuth-Morris-Pratt algorithm. ALG 13.1–13.2, JeffE's notes, 7.1, 7.4-7.6, KMP slides |
| 12. 10. | A few more words about AI (slides). KMP automaton construction ALG 13.2, KMP slides, part 2. Searching for more needles: Aho-Corasick ALG 13.3, JeffE's notes, 7.2, reference for AC: slides. Preview of Rabin-Karp ALG 13.4 |
| 19. 10. | Rabin-Karp ALG 13.4, JeffE's notes, 7.3. Network flows intro, Ford-Fulkerson's algorithm; it terminates for integer and rational capacities, but may not for real ones. ALG 14.1–14.2, JeffE's notes, 10.1-10.4. Practice: Rolling Hash, Augment! |
| 26. 10. | Plan: Correctness of Ford-Fulkerson's algorithm (when it stops, the flow is maximum) ALG 14.2, JeffE's notes, 10.1-10.4. Dinic's algorithm ALG 14.4, slides of Honza Hubička, CP-algorithms, NetworkX notebook. |