teaching:ads12122_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:ads12122_lecture [2022/03/03 17:43] – Martin Koutecky | teaching:ads12122_lecture [2022/05/23 11:45] (aktuální) – exam Martin Koutecky | ||
---|---|---|---|
Řádek 10: | Řádek 10: | ||
| 17. 2.| Richest subsequence. Attempts at defining an algorithm. Von Neumann' | | 17. 2.| Richest subsequence. Attempts at defining an algorithm. Von Neumann' | ||
| 24. 2. | Why graphs problems, DFS: identifying connected components, pre- and post-orderings, | | 24. 2. | Why graphs problems, DFS: identifying connected components, pre- and post-orderings, | ||
- | | 2. 3. | DFS: topological ordering, detecting strongly connected components. **[A, remainder of Chap 3]**, very brief intro to BFS **[A, beginning of Chap 4]**. Recording to come later.| | + | | 2. 3. | DFS: topological ordering, detecting strongly connected components. **[A, remainder of Chap 3]**, very brief intro to BFS **[A, beginning of Chap 4]**. [[https:// |
- | {{page> | + | | 9. 3. | Shortest paths: BFS, Dijkstra, general relaxation algorithm, Bellman-Ford, |
- | + | | 16. 3. | Shortest paths: recap of Bellman-Ford; | |
- | /* | + | | 23. 3. | Minimum Spanning Trees: Cut property |
- | | 25. 2.| Základní grafové algoritmy: prohledávání do šířky (BFS), prohledávání do hloubky (DFS) na neorientovaném grafu, detekce mostů, DFS na orientovaném grafu **[L 5.1-5.6]**| | + | | 30. 3. | Union-Find Data structure |
- | | 3. 3.| Pokračování DFS: topologické číslování; | + | | 6. 4. | AVL tree rebalancing, |
- | | 10. 3.| Nejkratší cesty: Dijkstrův algoritmus pořádně; obecný relaxační algoritmus; | + | | 13. 4. | $(a,b)$-trees [[https://cs.lmu.edu/~ray/notes/ |
- | | 17. 3.| Minimální kostry: Jarníkův | + | | 20. 4. | Amortized analysis, hashing |
- | | 24. 3.| Stromové datové struktury: binární vyhledávací stromy, AVL-stromy | + | | 27. 4. | Universal, perfect hashing |
- | | 31. 3.| $(a,b)$-stromy, červeno-černé stromy **[L 8]**[[https:// | + | | 4. 5. | Divide & conquer -- Karatsuba' |
- | | 7. 4.| rekapitulace LLRB, amortizace, úvod do hešování **[L 9.1-9.2; 11.3]** | + | | 18. 5. | Sorting lower bound [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/ |
- | | 14. 4.| Hešování s otevřenou adresací, univerzální hešování **[L 11.3-11.4]**, [[ | + | |
- | https://stream.cuni.cz/cs/Detail/4279|video přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoB3OsgQAyUXxTRt5BeNqVVWw? | + | |
- | | 21. 4.| Rozděl a panuj - úvod, kuchařková věta, násobení dlouhých čísel **[L 10]**, [[https:// | + | |
- | | 28. 4.| Rozděl a panuj - hledání medánu v lineárním čase; úvod do dynamického programování **[L 10.6-10.9, L 12.1-12.2]** [[https:// | + | |
- | | 5. 5.| Dynamické programování - Editační vzdálenost; | + | |
+ | {{page> | ||
+ | {{ : | ||
- | {{ : | ||
- | ===== Zkouška ADS 1 / 2020 ===== | + | ====== ADS1 Exam / 2022 ====== |
- | Na zkoušce budou zadány | + | The exam will consist of: |
- | - Dva příklady na algoritmy či datové struktury z přednášky | + | - 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. |
- | - Dvě úlohy podobné těm ze cvičení | + | - 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) |
- | === Hodnocení === | + | The form of the exam is that you will come, get the question sheet, and work on the answers. Once you are finished with one of the answers, you hand it in, I will read it, point out anything which is missing / incorrect, give you hints if needed, and you can revise it. At some point either you will reach a correct solution, or you won’t want to try to improve it again, or I will feel like I can’t give you any more hints, and then we’ll reach some grade. |
- | **Na 3** stačí znát definice a algoritmy a nechat se dostrkat k řešení aspoň jedné úlohy (nebo ji vyřešit neefektivně). | + | ==== Grading ==== |
- | **Na 2** je potřeba umět řešit úlohy s nápovědou, | + | **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). |
- | **Na 1** je potřeba i rozbor algoritmů (správnost a složitost včetně důkazů tvrzení) | + | **To get a 2** you need to be able to solve the tasks with some hints, or find a suboptimal |
- | === Okruhy === | + | **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.) |
- | **Pozor**, okruhy níže // | + | ===== 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. |
- | | + | |
- | | + | |
- | | + | |
- | * Floyd-Warshallův algoritmus — půltéma | + | |
- | * Jarníkův algoritmus | + | |
- | * Borůvkův algoritmus | + | |
- | * Kruskalův algoritmus + Union-Find pomocí keříků | + | |
- | * BVS obecně | + | |
- | * AVL stromy | + | |
- | * $(a,b)$-stromy | + | |
- | * Červeno-černé stromy | + | |
- | * Hešování s přihrádkami | + | |
- | * Hešování s otevřenou adresací | + | |
- | * Univerzální hešování | + | |
- | * Kuchařková věta, rozbor algoritmu rozděl | + | |
- | * Násobení dlouhých čísel pomocí rozděl a panuj; Strassenův algoritmus (idea) | + | |
- | * LinearSelect | + | |
- | * QuickSort v průměrném případě | + | |
- | * Editační vzdálenost | + | |
- | * Dolní odhady: binární vyhledávání, třídění v srovnávacím modelu | + | |
- | */ | + | |
+ | * DFS applications: | ||
+ | * Dijkstra’s algorithm | ||
+ | * Bellman-Ford’s algorithm | ||
+ | * Floyd-Warshall’s algorithm (small topic) | ||
+ | * Jarník’s algorithm | ||
+ | * Borůvka’s algorithm | ||
+ | * Kruskal’s algoritmus + Union-Find data structure using trees | ||
+ | * Binary Search Trees (BSTs) in general | ||
+ | * AVL trees | ||
+ | * $(a, | ||
+ | * Red-black trees – we covered these very briefly, but you should be able to describe the bijection between LLRBs and $(2, | ||
+ | * Hashing with chaining | ||
+ | * Hashing with open addressing (warning, I did this at the tutorial; if you don’t understand it, please read JeffE’s notes) | ||
+ | * Universal hashing | ||
+ | * Master theorem – analyzing the complexity of Divide & Conquer algorithms using the recursion tree | ||
+ | * Integer multiplication using Karatsuba’s algorithm | ||
+ | * MomSelect (finding the $k$-th smallest element in an array in linear time) | ||
+ | * Edit Distance dynamic programming algorithm | ||
+ | * Longest Increasing Subsequence dynamic programming algorithm | ||
+ | * 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) | ||
teaching/ads12122_lecture.1646325784.txt.gz · Poslední úprava: 2022/03/03 17:43 autor: Martin Koutecky