| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:ads22627_lecture [2026/10/03 11:11] – table full width (removed float=left) Claude Cowork | teaching:ads22627_lecture [2026/11/16 15:06] (aktuální) – 16.11 as taught (FFT finished, circuits); 23.11 plan Claude Cowork |
|---|
| ====== Algorithms and Data Structures II 2026/27 -- Lecture ====== | ====== Algorithms and Data Structures II 2026/27 -- Lecture ====== |
| |
| I teach Algorithms and Data Structures II ([[https://is.cuni.cz/studium/predmety/index.php?id=ca693fd9cf8e9944b3721d7927be4b20&tid=&do=predmet&kod=NTIN061&skr=2022&fak=11320|NTIN061]]) every Monday at 15:40 at S3 (Malá strana). | I teach Algorithms and Data Structures II ([[https://is.cuni.cz/studium/predmety/index.php?do=predmet&kod=NTIN061|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. | 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. |
| |
| {{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100}} | **Practice:** small games and step-through playgrounds for most algorithms of the lecture, see [[#ads2_arcade|ADS2 Arcade]] below and the //Practice// links in the table. |
| ^ data ^ what was taught [resources] ^ | |
| | 5. 10.| Plan: String searching: Knuth-Morris-Pratt algorithm. [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-strings.pdf|JeffE's notes, 7.1, 7.4-7.6]]| | |
| |
| | {{tablelayout?colwidth="100px,800px"&rowsHeaderSource=1&rowsVisible=100}} |
| | ^ data ^ what was taught [resources] ^ |
| | | 28. 9. | No lecture: [[https://en.wikipedia.org/wiki/Wenceslaus_I,_Duke_of_Bohemia|St. Wenceslas Day]]| |
| | | 5. 10.| A few words about AI ([[https://iuuk.mff.cuni.cz/~koutecky/ads2/ai/|slides]]). String searching: Knuth-Morris-Pratt algorithm. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=327|ALG 13.1–13.2]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-strings.pdf|JeffE's notes, 7.1, 7.4-7.6]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/kmp/|KMP slides]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/zsprint.html|Failure Function Sprint]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/kmp/playground.html|KMP Playground]]| |
| | | 12. 10. | A few more words about AI ([[https://iuuk.mff.cuni.cz/~koutecky/ads2/ai2/|slides]]). KMP automaton construction [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=328|ALG 13.2]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/kmp/#/9|KMP slides, part 2]]. Searching for more needles: Aho-Corasick [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=333|ALG 13.3]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-strings.pdf|JeffE's notes, 7.2]], reference for AC: [[https://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Small02.pdf|slides]]. Preview of Rabin-Karp [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=338|ALG 13.4]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/acfail.html|Where Do I Fail?]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2/ac/playground.html|Aho-Corasick Playground]]| |
| | | 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!]]| |
| | | 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]]//| |
| /* | /* |
| | 7. 10. | String searching: Finished KMP, Aho-Corasick [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-strings.pdf|JeffE's notes, 7.2]], reference for AC: [[https://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Small02.pdf|slides]]| | | 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]]| |
| | 14. 10. | Rabin-Karp [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-strings.pdf|JeffE's notes, 7.3]], Network flows intro, Ford-Fulkerson's algorithm. [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf|JeffE's notes, 10.1-10.4]]| | | 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]]| |
| | 21. 10. | Plan: Correctness of Ford-Fulkerson's algorithm [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf|JeffE's notes, 10.1-10.4]]. Dinic's algorithm [[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]].| | | 14. 12. | Q&A about 3,3-SAT -> 3DM reduction. Classes P, NP; Cook's theorem. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=490|ALG 19.3–19.4]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-10.pdf|slides]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf|JeffE]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2-21122022.mkv|recording (2022)]]. Dealing with NP-hardness. IndSet is solvable on trees; coloring is solvable on interval graphs. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=499|ALG 19.5]]| |
| | 28. 10. | //No lecture: [[https://en.wikipedia.org/wiki/Czechoslovak_declaration_of_independence|Czechoslovak Independence Day]]//| | | 4. 1. | //Plan: Knapsack is solvable in pseudopolynomial time (=when input values are polynomially bounded). Approximation: 2-approximation algorithm for $\Delta$-TSP (on a complete graph and with $\Delta$-inequality). No $\alpha$-approximation for general TSP. Fully polynomial time approximation scheme (FPTAS) for Knapsack (downscaling values). [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=499|ALG 19.5–19.6]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-10.pdf|slides 1]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-11.pdf|slides 2]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2-04012023.mkv|recording (2022)]]. Practice: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/apx.html|Good Enough]]//| |
| | 4. 11. | Finish analysis of Dinic. Goldberg's push-relabel algorithm; [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-4.pdf|slides]], [[https://mj.ucw.cz/vyuka/1819/ads2/goldberg.pdf|notes]]| | |
| | 11. 11. | Multiplying polynomials quickly: FFT (Fast Fourier Transform). 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]]| | |
| | 18. 11. | Finish FFT algorithm. More notes on FFT. Begin parallel algorithms: fast addition. 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)]]| | |
| | 25. 11. | Cancelled; will be replaced Friday 29. 11. Plan: Parallel sorting. [[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/~hubicka/2020/adsII-12.pdf|slides]], **[CLRS 33.1-33.3]**| | |
| | 2. 12. | Line segment intersections [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-12.pdf|slides]]. Begin reductions, hardness.| | |
| | 9. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[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]].| | |
| | 16. 12. | Q&A about 3,3-SAT -> 3DM reduction. Classes P, NP; Cook's theorem. [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-10.pdf|slides]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf|JeffE]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2-21122022.mkv|recording (2022)]]. Dealing with NP-hardness. IndSet is solvable on trees; coloring is solvable on interval graphs.| | |
| | 6. 1. | //Plan: Knapsack is solvable in pseudopolynomial time (=when input values are polynomially bounded). Approximation: 2-approximation algorithm for $\Delta$-TSP (on a complete graph and with $\Delta$-inequality). No $\alpha$-approximation for general TSP. Fully polynomial time approximation scheme (FPTAS) for Knapsack (downscaling values). [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-10.pdf|slides 1]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-11.pdf|slides 2]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2-04012023.mkv|recording (2022)]]//| | |
| */ | */ |
| |
| |
| | |
| | ====== ADS2 Arcade ====== |
| | |
| | Small games for the algorithms of the lecture: [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/|ADS2 Arcade]] (all games on one page). Notation follows the ALG book. |
| | |
| | * **Strings:** 🏃 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/zsprint.html|Failure Function Sprint]] (KMP, ALG 13.2) · 🔬 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/kmp/playground.html|KMP Playground]] (KMP, step through, ALG 13.2) · 🌳 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/acfail.html|Where Do I Fail?]] (Aho-Corasick, ALG 13.3) · 🔭 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/ac/playground.html|Aho-Corasick Playground]] (Aho-Corasick, step through, ALG 13.3) · 🎲 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/rabinkarp.html|Rolling Hash]] (Rabin-Karp, ALG 13.4) |
| | * **Flows:** 🚰 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/flow.html|Augment!]] (Ford-Fulkerson, Dinic, ALG 14.2, 14.4) · 🎓 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/match.html|Thesis Match]] (bipartite matching, ALG 14.3) · ⛰️ [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/goldberg.html|Downhill]] (Goldberg, ALG 14.5) |
| | * **Parallel algorithms:** ➕ [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/carry.html|Carry Lookahead]] (parallel addition, ALG 15.2) · 🔀 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/sortnet.html|Comparator Lab]] (sorting networks, ALG 15.3) |
| | * **Geometry, FFT:** 🍎 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/hull.html|Fence the Orchard]] (convex hull, sweep line, ALG 16.1–16.2) · 🌀 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/fft.html|Square Dance]] (FFT, ALG 17.1–17.3) |
| | * **Hardness:** 🔺 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/reduce.html|One per Triangle]] (3-SAT → IndSet, ALG 19.2) · 🧳 [[https://iuuk.mff.cuni.cz/~koutecky/ads2/play/apx.html|Good Enough]] (approximation, ALG 19.6) |
| |
| {{page>teaching:bits:resources_ads1}} | {{page>teaching:bits:resources_ads1}} |
| * Pseudopolynomial algorithm for Knapsack; FPTAS for Knapsack. | * Pseudopolynomial algorithm for Knapsack; FPTAS for Knapsack. |
| */ | */ |
| | |
| | |
| |
| |