| Obě strany předchozí revizePředchozí verze | |
| teaching:ads22627_lecture [2026/11/09 15:09] – 9.11 taught; 16.11 plan Claude Cowork | teaching:ads22627_lecture [2026/11/16 15:06] (aktuální) – 16.11 as taught (FFT finished, circuits); 23.11 plan Claude Cowork |
|---|
| | 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)| | | 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]]| | | 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. | //Plan: Finish FFT: the inverse DFT, and polynomial multiplication from it. More notes on FFT. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=435|ALG 17.1–17.3]]. 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]]//| | | 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]]//| |
| /* | /* |
| | 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]]| |