Uživatelské nástroje

Nástroje pro tento web


teaching:ads22627_lecture

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
Následující verze
Předchozí verze
teaching:ads22627_lecture [2026/11/02 20:15] – 2.11. taught; 9.11. plan (FFT) Claude Coworkteaching:ads22627_lecture [2026/11/16 15:06] (aktuální) – 16.11 as taught (FFT finished, circuits); 23.11 plan Claude Cowork
Řádek 14: Řádek 14:
 | 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. | 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]]. 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. | //Plan: Multiplying polynomials quickly: representing a polynomial by its values (its graph), a sketch of the recursive algorithm. A review of complex numbers. The Fast Fourier Transform (FFT) and its inverse. [[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]]//|+| 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]]//|
 /* /*
-| 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]]|
teaching/ads22627_lecture.1793650539.txt.gz · Poslední úprava: autor: Claude Cowork