Rozdíly

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

--- teaching:ads22223_lecture [2022/12/21 18:25] – Martin Koutecky
+++ teaching:ads22223_lecture [2023/01/09 12:41] (aktuální) – Martin Koutecky
@@ Řádek 20: / Řádek 20: @@
 | 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]]|
 {{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>)
-/*
-====== ADS1 Exam / 2022 ======
+====== ADS2 Exam / 2023 ======
 The exam will consist of:
-  - Two questions about an algorithm or a data structure from the lecture – describing the algorithm or data structure, proving they are correct, giving the complexity analysis.
+  - Two questions about an algorithm or a data structure from the lecture – describing the algorithm or data structure, proving they are correct, giving the complexity analysis. (With "big" topics I will ask about a specific part of an algorithm, or for an overview of the algorithm. No need to reproduce 2 lectures worth of material as your first answer.)
   - Two tasks similar to those from the tutorial – either apply an algorithm / data structure from the lecture to some problem (need to model the problem appropriately) OR adapt the algorithm / data structure to solve some problem (need to understand how it works internally to be able to adapt it appropriately)
@@ Řádek 47: / Řádek 48: @@
 **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.
-  * BFS, DFS and their edge classifications
+  * String searching -- problem definition, basic notions and lemmas
-  * DFS applications: topological sorting, detecting strongly connected components
+    * Knuth-Morris-Pratt Algorithm
-  * Dijkstra’s algorithm
+    * Aho-Corasick Algorithm
-  * Bellman-Ford’s algorithm
+    * Rabin-Karp Algorithm
-  * Floyd-Warshall’s algorithm (small topic)
+  * Network Flows -- problem definition, notions, lemmas
-  * Jarník’s algorithm
+    * Ford-Fulkerson
-  * Borůvka’s algorithm
+    * Dinitz
-  * Kruskal’s algoritmus + Union-Find data structure using trees
+    * Goldberg
-  * Binary Search Trees (BSTs) in general
+  * Parallel Algorithms / Circuits
-  * AVL trees
+    * Fast Addition
-  * $(a,b)$-trees
+    * Fast Sorting
-  * Red-black trees – we covered these very briefly, but you should be able to describe the bijection between LLRBs and $(2,4)$-trees
+  * Geometric Algorithms
-  * Hashing with chaining
+    * Convex Hull
-  * Hashing with open addressing (warning, I did this at the tutorial; if you don’t understand it, please read JeffE’s notes)
+    * Line Segment Intersections
-  * Universal hashing
+  * FFT: definitions, algorithm, how to multiply polynomials quickly
-  * Master theorem – analyzing the complexity of Divide & Conquer algorithms using the recursion tree
+  * Reductions
-  * Integer multiplication using Karatsuba’s algorithm
+    * Definitions of most important NP-hard problems: SAT, IS, VC, Clique, 3DM, SubsetSum
-  * MomSelect (finding the $k$-th smallest element in an array in linear time)
+    * P, NP, NP-complete, NP-hard
-  * Edit Distance dynamic programming algorithm
+    * Cook's theorem
-  * Longest Increasing Subsequence dynamic programming algorithm
+  * Dealing with NP-hardness
-  * Lower bounds: searching in a sorted array is $\Omega(\log n)$, sorting is $\Omega(n \log n)$ (only applies to deterministic and comparison-based algorithms)
+    * IndSet on Trees
+    * Coloring of Interval Graphs
+    * Approximation algorithms (definition)
+    * $2$-approximation of $\Delta$-TSP
+    * Non-existence of an $O(1)$-approximation for (unrestricted) TSP
+    * Pseudopolynomial algorithm for Knapsack; FPTAS for Knapsack.
-*/