| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:ads22627_lecture [2026/10/26 15:18] – Arcade section; per-row Practice links; next week's row in italics; 'net flow' Claude Cowork | teaching:ads22627_lecture [2026/11/16 15:06] (aktuální) – 16.11 as taught (FFT finished, circuits); 23.11 plan Claude Cowork |
|---|
| | 19. 10. | Rabin-Karp [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=338|ALG 13.4]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-strings.pdf|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. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=361|ALG 14.1–14.2]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf|JeffE's notes, 10.1-10.4]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/rabinkarp.html|Rolling Hash]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/flow.html|Augment!]]| | | 19. 10. | Rabin-Karp [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=338|ALG 13.4]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-strings.pdf|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. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=361|ALG 14.1–14.2]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf|JeffE's notes, 10.1-10.4]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/rabinkarp.html|Rolling Hash]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/flow.html|Augment!]]| |
| | 26. 10. | A few words about AI: The Hackening, verifiable software ([[https://iuuk.mff.cuni.cz/~koutecky/ads2/ai3/|slides]]). Correctness of Ford-Fulkerson's algorithm (when it stops, the flow is maximum) [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=364|ALG 14.2]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf|JeffE's notes, 10.1-10.4]]. Maximum matching in bipartite graphs via flows (unit capacities) [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=370|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). [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=372|ALG 14.4]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-3.pdf|slides of Honza Hubička]], [[https://cp-algorithms.com/graph/dinic.html#finding-blocking-flow|CP-algorithms]], [[https://networkx.org/nx-guides/content/algorithms/flow/dinitz_alg.html|NetworkX notebook]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/match.html|Thesis Match]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/flow.html|Augment!]]| | | 26. 10. | A few words about AI: The Hackening, verifiable software ([[https://iuuk.mff.cuni.cz/~koutecky/ads2/ai3/|slides]]). Correctness of Ford-Fulkerson's algorithm (when it stops, the flow is maximum) [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=364|ALG 14.2]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf|JeffE's notes, 10.1-10.4]]. Maximum matching in bipartite graphs via flows (unit capacities) [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=370|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). [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=372|ALG 14.4]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-3.pdf|slides of Honza Hubička]], [[https://cp-algorithms.com/graph/dinic.html#finding-blocking-flow|CP-algorithms]], [[https://networkx.org/nx-guides/content/algorithms/flow/dinitz_alg.html|NetworkX notebook]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/match.html|Thesis Match]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/flow.html|Augment!]]| |
| | 2. 11. | //Plan: Finish analysis of Dinic (the layered network gets longer in every phase, so at most $n-1$ phases). Goldberg's push-relabel algorithm; [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=379|ALG 14.5]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-4.pdf|slides]], [[https://mj.ucw.cz/vyuka/1819/ads2/goldberg.pdf|notes]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/goldberg.html|Downhill]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/flow.html|Augment!]] (Dinic mode)//| | | 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. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=379|ALG 14.5]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-4.pdf|slides]], [[https://mj.ucw.cz/vyuka/1819/ads2/goldberg.pdf|notes]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/goldberg/|Goldberg slides]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/goldberg.html|Downhill]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/flow.html|Augment!]] (Dinic mode)| |
| | | 9. 11. | A few words about AI: misalignment ([[https://iuuk.mff.cuni.cz/~koutecky/ads2/ai4/|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). [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=435|ALG 17.1–17.3]], slides [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-7.pdf|1]] [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-8.pdf|2]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/A-fft.pdf|JeffE's notes]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/complex/|complex numbers slides]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/fft.html|Square Dance]]| |
| | | 16. 11. | Finished FFT: the inverse DFT, and multiplying polynomials with it. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=435|ALG 17.1–17.3]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/fft/|FFT slides]]. Parallel algorithms: Boolean circuits; a circuit for majority; the OR of $n$ inputs in depth $O(\log n)$. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=393|ALG 15.1]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-5.pdf|slides]]. Began fast addition (to be finished next time). Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/fft.html|Square Dance]]| |
| | | 23. 11. | //Plan: Finish fast addition (carry lookahead). [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=398|ALG 15.2]], [[https://ti.inf.ethz.ch/ew/courses/APC22/Chapter_6.pdf|notes for addition (6.1)]]. Parallel sorting. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=404|ALG 15.3]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-6.pdf|slides]], [[http://users.wfu.edu/choss/CUDA/docs/Lecture%2010.pdf|more slides]]. Geometric algorithms: convex hull, line segment intersections [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=413|ALG 16.1–16.2]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-12.pdf|slides]], **[CLRS 33.1-33.3]**. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/carry.html|Carry Lookahead]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/sortnet.html|Comparator Lab]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/hull.html|Fence the Orchard]]//| |
| /* | /* |
| | 9. 11. | Multiplying polynomials quickly: FFT (Fast Fourier Transform). [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=435|ALG 17.1–17.3]], slides [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-7.pdf|1]] [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-8.pdf|2]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/A-fft.pdf|JeffE's notes]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/fft.html|Square Dance]]| | |
| | 16. 11. | Finish FFT algorithm. More notes on FFT. Begin parallel algorithms: fast addition. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=393|ALG 15.1–15.2]], slides: [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-5.pdf|1]], ; [[https://ti.inf.ethz.ch/ew/courses/APC22/Chapter_6.pdf|notes for addition (6.1)]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/fft.html|Square Dance]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/carry.html|Carry Lookahead]]| | |
| | 23. 11. | Plan: Parallel sorting. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=404|ALG 15.3]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-6.pdf|slides]], [[http://users.wfu.edu/choss/CUDA/docs/Lecture%2010.pdf|more slides]]. Geometric algorithms: convex hull, line segment intersections [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=413|ALG 16.1–16.2]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-12.pdf|slides]], **[CLRS 33.1-33.3]**. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/sortnet.html|Comparator Lab]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/hull.html|Fence the Orchard]]| | |
| | 30. 11. | Line segment intersections [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=418|ALG 16.2]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-12.pdf|slides]]. Begin reductions, hardness. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=479|ALG 19.1]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/hull.html|Fence the Orchard]]| | | 30. 11. | Line segment intersections [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=418|ALG 16.2]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-12.pdf|slides]]. Begin reductions, hardness. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=479|ALG 19.1]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/hull.html|Fence the Orchard]]| |
| | 7. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=482|ALG 19.2]], [[https://stream.cuni.cz/cs/Detail/18529|recording (2022)]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-9.pdf|slides]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf|JeffE (more than you asked for)]]. [[https://bluehorn07.github.io/2022/05/13/reduction-3/|Very good pictures for the reduction 3,3-SAT -> 3DM]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/reduce.html|One per Triangle]]| | | 7. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=482|ALG 19.2]], [[https://stream.cuni.cz/cs/Detail/18529|recording (2022)]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-9.pdf|slides]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf|JeffE (more than you asked for)]]. [[https://bluehorn07.github.io/2022/05/13/reduction-3/|Very good pictures for the reduction 3,3-SAT -> 3DM]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/reduce.html|One per Triangle]]| |