teaching:ads22425_lecture
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze | ||
| teaching:ads22425_lecture [2024/12/07 01:29] – exam Martin Koutecky | teaching:ads22425_lecture [2025/01/23 22:18] (aktuální) – Martin Koutecky | ||
|---|---|---|---|
| Řádek 17: | Řádek 17: | ||
| | 25. 11. | Cancelled; will be replaced Friday 29. 11. Plan: Parallel sorting. [[https:// | | 25. 11. | Cancelled; will be replaced Friday 29. 11. Plan: Parallel sorting. [[https:// | ||
| | 2. 12. | Line segment intersections [[https:// | | 2. 12. | Line segment intersections [[https:// | ||
| - | | 9. 12. | // | + | | 9. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[https:// |
| - | | 16. 12. | // | + | | 16. 12. | Q&A about 3, |
| - | | 6. 1. | // | + | | 6. 1. | // |
| Řádek 47: | Řádek 47: | ||
| 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' | 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' | ||
| + | **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 ===== | ||
| Řádek 59: | Řádek 65: | ||
| * Dinitz | * Dinitz | ||
| * Goldberg | * Goldberg | ||
| + | * FFT: definitions, | ||
| * Parallel Algorithms / Circuits | * Parallel Algorithms / Circuits | ||
| * Fast Addition | * Fast Addition | ||
| Řádek 65: | Řádek 72: | ||
| * Convex Hull | * Convex Hull | ||
| * Line Segment Intersections | * Line Segment Intersections | ||
| - | * FFT: definitions, | ||
| * Reductions | * Reductions | ||
| * Definitions of most important NP-hard problems: SAT, IS, VC, Clique, 3DM, SubsetSum | * Definitions of most important NP-hard problems: SAT, IS, VC, Clique, 3DM, SubsetSum | ||
| * P, NP, NP-complete, | * P, NP, NP-complete, | ||
| - | * Cook's theorem | + | * Cook's theorem |
| * Dealing with NP-hardness | * Dealing with NP-hardness | ||
| * IndSet on Trees | * IndSet on Trees | ||
| * Coloring of Interval Graphs | * Coloring of Interval Graphs | ||
| - | * Approximation algorithms (definition) | + | * Approximation algorithms |
| * $2$-approximation of $\Delta$-TSP | * $2$-approximation of $\Delta$-TSP | ||
| * Non-existence of an $O(1)$-approximation for (unrestricted) TSP | * Non-existence of an $O(1)$-approximation for (unrestricted) TSP | ||
teaching/ads22425_lecture.1733531351.txt.gz · Poslední úprava: 2024/12/07 01:29 autor: Martin Koutecky