| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:ads22425_lecture [2024/12/10 01:14] – 9. 12. 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. | //Plan: 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)]]//| | | 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: Dealing with NP-hardness. IndSet is solvable on trees; coloring is solvable on interval graphs; 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)]]//| |
| |
| |
| 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.** | 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 ===== | ===== Topics ===== |
| |
