teaching:ads22627_lecture
Algorithms and Data Structures II 2026/27 -- Lecture
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: small games and step-through playgrounds for most algorithms of the lecture, see ADS2 Arcade below and the Practice links in the table.
| 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. Practice: Failure Function Sprint, KMP Playground |
| 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. Practice: Where Do I Fail?, Aho-Corasick Playground |
| 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. | A few words about AI: The Hackening, verifiable software (slides). Correctness of Ford-Fulkerson's algorithm (when it stops, the flow is maximum) ALG 14.2, JeffE's notes, 10.1-10.4. Maximum matching in bipartite graphs via flows (unit capacities) ALG 14.3. Dinic's algorithm: net flow $f^*(uv) = f(uv) - f(vu)$; a flow $f$ in $N$ plus a flow $g$ in the residual network gives a flow of size $|f| + |g|$; blocking flow, layered network and how to compute it; the algorithm (analysis next time). ALG 14.4, slides of Honza Hubička, CP-algorithms, NetworkX notebook. Practice: Thesis Match, Augment! |
| 2. 11. | Finished the analysis of Dinic (the layered network gets longer in every phase, so at most $n-1$ phases). Goldberg's algorithm: preflow, excess, heights, pushing and raising; behaviour on a narrowing path; always choosing the highest vertex with excess (faster, not proved); full proof of correctness and of the $O(n^2m)$ bound. ALG 14.5, slides, notes, Goldberg slides. Practice: Downhill, Augment! (Dinic mode) |
| 9. 11. | A few words about AI: misalignment (slides). Multiplying polynomials quickly: representing a polynomial by its values (its graph). A review of complex numbers. The Fast Fourier Transform (FFT) algorithm. Sketch: FFT computes the Discrete Fourier Transform (DFT), a linear transformation, which can be inverted (how this gives polynomial multiplication: next time). ALG 17.1–17.3, slides 1 2, JeffE's notes, complex numbers slides. Practice: Square Dance |
| 16. 11. | Finished FFT: the inverse DFT, and multiplying polynomials with it. ALG 17.1–17.3, FFT slides. Parallel algorithms: Boolean circuits; a circuit for majority; the OR of $n$ inputs in depth $O(\log n)$. ALG 15.1, slides. Began fast addition (to be finished next time). Practice: Square Dance |
| 23. 11. | Plan: Finish fast addition (carry lookahead). ALG 15.2, notes for addition (6.1). Parallel sorting. ALG 15.3, slides, more slides. Geometric algorithms: convex hull, line segment intersections ALG 16.1–16.2, slides, [CLRS 33.1-33.3]. Practice: Carry Lookahead, Comparator Lab, Fence the Orchard |
ADS2 Arcade
Small games for the algorithms of the lecture: ADS2 Arcade (all games on one page). Notation follows the ALG book.
- Strings: 🏃 Failure Function Sprint (KMP, ALG 13.2) · 🔬 KMP Playground (KMP, step through, ALG 13.2) · 🌳 Where Do I Fail? (Aho-Corasick, ALG 13.3) · 🔭 Aho-Corasick Playground (Aho-Corasick, step through, ALG 13.3) · 🎲 Rolling Hash (Rabin-Karp, ALG 13.4)
- Flows: 🚰 Augment! (Ford-Fulkerson, Dinic, ALG 14.2, 14.4) · 🎓 Thesis Match (bipartite matching, ALG 14.3) · ⛰️ Downhill (Goldberg, ALG 14.5)
- Parallel algorithms: ➕ Carry Lookahead (parallel addition, ALG 15.2) · 🔀 Comparator Lab (sorting networks, ALG 15.3)
- Geometry, FFT: 🍎 Fence the Orchard (convex hull, sweep line, ALG 16.1–16.2) · 🌀 Square Dance (FFT, ALG 17.1–17.3)
- Hardness: 🔺 One per Triangle (3-SAT → IndSet, ALG 19.2) · 🧳 Good Enough (approximation, ALG 19.6)
Useful Resources
- [ALG] Algorithm Labyrinth Guide by Mareš and Valla. EXPERIMENTAL: this is a work-in-progress, AI-generated translation of the excellent Czech textbook Průvodce Labyrintem Algoritmů. It may be rough or even wrong (due to translation issues); I'll be working on improving it, especially the parts directly relevant to covered material.
- [A] Algorithms by Dasgupta, Papadimitriou, and Vazirani
- [JE] Algorithms by Jeff Erickson (the page contains various PDFs suitable for screen, printing etc.)
- [CLRS] Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. Find it on libgen
- Notes from Andrej Perković (100MB file) (no guarantee of correctness, email him if you find bugs: arachneen_octogone.0c@icloud.com)
teaching/ads22627_lecture.txt · Poslední úprava: autor: Claude Cowork
