| Obě strany předchozí revizePředchozí verze | |
| teaching:ads22425_lecture [2025/01/21 22:49] – [Cheating] Martin Koutecky | teaching:ads22425_lecture [2025/01/23 22:18] (aktuální) – Martin Koutecky |
|---|
| | 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]**| | | 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.| | | 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)]]. Very good pictures for the reduction 3,3-SAT -> 3DM [[https://rntlqvnf.github.io/assets/lecture/algo/np/gadget.PNG|1]], [[https://rntlqvnf.github.io/assets/lecture/algo/np/gad.PNG|2]], [[https://rntlqvnf.github.io/assets/lecture/algo/np/cla.PNG|3]], [[https://rntlqvnf.github.io/assets/lecture/algo/np/cla_2.PNG|4]], [[https://rntlqvnf.github.io/assets/lecture/algo/np/cla_3.PNG|5]]; ([[https://rntlqvnf.github.io/lecture%20notes/algorithm-np-1/|source (Korean)]])| | | 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.| | | 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)]]//| | | 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)]]//| |
