MK's wiki

Uživatelské nástroje

Nástroje pro tento web

Historie:
teaching:ads22425_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

Obě strany předchozí revizePředchozí verze
Následující verze		Předchozí verze
teaching:ads22425_lecture [2024/11/26 18:30] – Martin Kouteckyteaching:ads22425_lecture [2025/01/23 22:18] (aktuální) – Martin Koutecky
Řádek 16: Řádek 16:
 | 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)]]| | 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)]]|
 | 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. | //Plan: 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)]]. [[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.| 
 +| 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)]]//|
  
-/* 
- Geometric algorithms: convex hull,  
- 
-| 14. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[https://stream.cuni.cz/cs/Detail/18529|recording]], [[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)]]| 
-| 21. 12. | 3,3-SAT reduces to 3DM. 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]]| 
-| 4. 1. | 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]]| 
-*/ 
  
  
Řádek 30: Řádek 26:
   * {{ :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>)   * {{ :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 ======
- +
-====== ADS2 Exam / 2023 ======+
  
 The exam will consist of: The exam will consist of:
Řádek 43: Řádek 37:
 ==== Grading ==== ==== Grading ====
  
-**To get a 3** it suffices to know definitions and algorithms / data structures and (with hints) finish at least one of the “type 2” tasks (perhaps suboptimally).+**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 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.
Řádek 49: Řádek 43:
 **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.) **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 ===== ===== 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 lecture.+**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   * String searching -- problem definition, basic notions and lemmas
Řádek 61: Řádek 65:
     * Dinitz     * Dinitz
     * Goldberg     * Goldberg
 +  * FFT: definitions, algorithm, how to multiply polynomials quickly
   * Parallel Algorithms / Circuits   * Parallel Algorithms / Circuits
     * Fast Addition     * Fast Addition
Řádek 67: Řádek 72:
     * Convex Hull     * Convex Hull
     * Line Segment Intersections     * Line Segment Intersections
-  * FFT: definitions, algorithm, how to multiply polynomials quickly 
   * 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, NP-hard     * P, NP, NP-complete, NP-hard
-    * Cook's theorem+    * Cook's theorem *(statement only)*
   * 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 *(definition)*
     * $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
     * Pseudopolynomial algorithm for Knapsack; FPTAS for Knapsack.     * Pseudopolynomial algorithm for Knapsack; FPTAS for Knapsack.
- 
-*/ 
  
  
teaching/ads22425_lecture.1732642202.txt.gz · Poslední úprava: 2024/11/26 18:30 autor: Martin Koutecky