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

Následující verze
Předchozí verze
teaching:ads22627_lecture [2026/10/03 11:01] – vytvořeno Martin Kouteckyteaching:ads22627_lecture [2026/11/16 15:06] (aktuální) – 16.11 as taught (FFT finished, circuits); 23.11 plan Claude Cowork
Řádek 1: Řádek 1:
-bla+====== Algorithms and Data Structures II 2026/27 -- Lecture ====== 
 + 
 +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. 
 + 
 +**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. 
 + 
 +{{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]]//| 
 +/* 
 +| 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]]| 
 +| 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]]| 
 +| 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]]//| 
 +*/ 
 + 
 + 
 + 
 +====== 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}} 
 + 
 +  * {{ :teaching:ads22223:ads2_lecture_notes.pdf |Notes from Andrej Perković}} (**100MB file**) (no guarantee of correctness, email him if you find bugs: <arachneen_octogone.0c@icloud.com>) 
 + 
 +/* 
 +====== ADS2 Exam / 2025 ====== 
 + 
 +The exam will consist of: 
 + 
 +  - Two questions about an algorithm or a data structure from the lecture – describing the algorithm or data structure, proving they are correct, giving the complexity analysis. (With "big" topics I will ask about a specific part of an algorithm, or for an overview of the algorithm. No need to reproduce 2 lectures worth of material as your first answer.) 
 +  - Two tasks similar to those from the tutorial – either apply an algorithm / data structure from the lecture to some problem (need to model the problem appropriately) OR adapt the algorithm / data structure to solve some problem (need to understand how it works internally to be able to adapt it appropriately) 
 + 
 +The form of the exam is that you will come, get the question sheet, and work on the answers. Once you are finished with one of the answers, you hand it in, I will read it, point out anything which is missing / incorrect, give you hints if needed, and you can revise it. At some point either you will reach a correct solution, or you won’t want to try to improve it again, or I will feel like I can’t give you any more hints, and then we’ll reach some grade. 
 + 
 +==== Grading ==== 
 + 
 +**To get a 3** it roughly suffices to (operationally!) know definitions and algorithms / data structures and (with hints) finish at least one of the “type 2” tasks (perhaps suboptimally). 
 + 
 +**To get a 2** you need to be able to solve the tasks with some hints, or find a suboptimal (complexity) algorithm. If we proved some intermediate claims during the lecture, and these are used in the proofs of correctness/complexity, you need to at least know the statements of these claims. 
 + 
 +**To get a 1** you need to analyze the algorithms (correctness and complexity) including the proofs, and you need to be able to solve the “type 2” tasks mostly independently. (Advice like “try dynamic programming” and similar is still fine though.) 
 + 
 +===== Cheating ===== 
 + 
 +I am extremely annoyed by people trying to cheat at the exam, and if I see anything fishy that you don't satisfactorily explain at the moment, you have failed the exam, you will be reported, and you won't have another chance at taking the exam with me. **Don't cheat.** 
 + 
 +**Update Jan 21, 2025:** from now on the following rules apply at the exam: 
 + 
 +  - You sit at the very end of the work desk, and your phone is at the very other end of the desk. 
 +  - Nothing else except your phone, pen, food, and drink is allowed to be on your desk, in particular no bags or clothing. All bags and clothing are on the seats at the other end of the desk. 
 +  - The exam may be long, so if you know you'll need to eat, bring the food with you. You won't be able to go buy food or drink during the exam. There is a tap with drinking water in the room. 
 +  - You can go to the bathroom, but only one person is allowed to be out of the room at any given point in time, and when you leave and when you come again, you need to sign yourself into a sheet and record the time you left / came back. When you go to the bathroom, only go to the bathroom and don't talk with anyone else. If you do, I will consider it cheating automatically. 
 +===== Topics ===== 
 + 
 +**Disclaimer:** the topics below are NOT specific instances of “type 1” questions. It is clear that some topics are wider and some narrower. However, if you have a good understanding of all the topics below, you should not be surprised by anything during the exam. 
 + 
 +  * String searching -- problem definition, basic notions and lemmas 
 +    * Knuth-Morris-Pratt Algorithm 
 +    * Aho-Corasick Algorithm 
 +    * Rabin-Karp Algorithm 
 +  * Network Flows -- problem definition, notions, lemmas 
 +    * Ford-Fulkerson 
 +    * Dinitz 
 +    * Goldberg 
 +  * FFT: definitions, algorithm, how to multiply polynomials quickly 
 +  * Parallel Algorithms / Circuits 
 +    * Fast Addition 
 +    * Fast Sorting 
 +  * Geometric Algorithms 
 +    * Convex Hull 
 +    * Line Segment Intersections 
 +  * Reductions 
 +    * Definitions of most important NP-hard problems: SAT, IS, VC, Clique, 3DM, SubsetSum 
 +    * P, NP, NP-complete, NP-hard 
 +    * Cook's theorem *(statement only)* 
 +  * Dealing with NP-hardness 
 +    * IndSet on Trees 
 +    * Coloring of Interval Graphs 
 +    * Approximation algorithms *(definition)* 
 +    * $2$-approximation of $\Delta$-TSP 
 +    * Non-existence of an $O(1)$-approximation for (unrestricted) TSP 
 +    * Pseudopolynomial algorithm for Knapsack; FPTAS for Knapsack. 
 +*/ 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
teaching/ads22627_lecture.1791025263.txt.gz · Poslední úprava: autor: Martin Koutecky