Rozdíly

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

--- teaching:ads22627_lecture [2026/10/03 11:05] – based on 24/25 version; old rows hidden (Claude) Claude Cowork
+++ teaching:ads22627_lecture [2026/10/03 12:25] (aktuální) – Martin Koutecky
@@ Řádek 1: / Řádek 1: @@
 ====== 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.
-{{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}}
+{{tablelayout?colwidth="100px,800px"&rowsHeaderSource=1&rowsVisible=100}}
 ^ data ^ what was taught [resources] ^
-| 30. 9.| 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]]|
+| 28. 9. | //No lecture: [[https://en.wikipedia.org/wiki/Wenceslaus_I,_Duke_of_Bohemia|St. Wenceslas Day]]//|
+| 5. 10.| Plan: String searching: Knuth-Morris-Pratt algorithm. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=321|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]]|
 /*
-| 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]]|
+| 12. 10. | String searching: Finished KMP, Aho-Corasick [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=327|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]]|
-| 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]]|
+| 19. 10. | Rabin-Karp [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=332|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. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=353|ALG 14.1–14.2]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf|JeffE's notes, 10.1-10.4]]|
-| 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]].|
+| 26. 10. | Plan: Correctness of Ford-Fulkerson's algorithm [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=355|ALG 14.2]], [[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/~koutecky/pruvodce-en-wip.pdf#page=364|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]].|
-| 28. 10. | //No lecture: [[https://en.wikipedia.org/wiki/Czechoslovak_declaration_of_independence|Czechoslovak Independence Day]]//|
+| 2. 11. | Finish analysis of Dinic. Goldberg's push-relabel algorithm; [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=370|ALG 14.5]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-4.pdf|slides]], [[https://mj.ucw.cz/vyuka/1819/ads2/goldberg.pdf|notes]]|
-| 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]]|
+| 9. 11. | Multiplying polynomials quickly: FFT (Fast Fourier Transform). [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=427|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]]|
-| 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]]|
+| 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=385|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)]]|
-| 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)]]|
+| 23. 11. | Plan: Parallel sorting. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=396|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=405|ALG 16.1–16.2]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-12.pdf|slides]], **[CLRS 33.1-33.3]**|
-| 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]**|
+| 30. 11. | Line segment intersections [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=410|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=469|ALG 19.1]]|
-| 2. 12. | Line segment intersections [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-12.pdf|slides]]. Begin reductions, hardness.|
+| 7. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[https://iuuk.mff.cuni.cz/~koutecky/pruvodce-en-wip.pdf#page=472|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]].|
-| 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]].|
+| 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=480|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=489|ALG 19.5]]|
-| 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.|
+| 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=492|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)]]//|
-| 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)]]//|
 */
@@ Řádek 26: / Řádek 27: @@
 {{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>)