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/04/13 15:28] – llrb Martin Koutecky | teaching:ads12122_lecture [2022/05/23 11:45] (aktuální) – exam Martin Koutecky | ||
---|---|---|---|
Řádek 17: | Řádek 17: | ||
| 6. 4. | AVL tree rebalancing, | | 6. 4. | AVL tree rebalancing, | ||
| 13. 4. | $(a, | | 13. 4. | $(a, | ||
+ | | 20. 4. | Amortized analysis, hashing [[https:// | ||
+ | | 27. 4. | Universal, perfect hashing [[https:// | ||
+ | | 4. 5. | Divide & conquer -- Karatsuba' | ||
+ | | 18. 5. | Sorting lower bound [[https:// | ||
{{page> | {{page> | ||
- | /* | + | {{ :teaching:ads12122:exam2122.pdf | Exam topics and format |
- | | 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]**| | + | |
- | | 3. 3.| Pokračování DFS: topologické číslování; | + | |
- | | 10. 3.| Nejkratší cesty: Dijkstrův algoritmus pořádně; obecný relaxační algoritmus; Bellman-Ford umí detekovat záporný cyklus; Floyd-Warshall umí spočítat matici vzdáleností **[L 6.1-6.4]**| | + | |
- | | 17. 3.| Minimální kostry: Jarníkův (Primův, Dijkstrův) algoritmus, Borůvkův algoritmus, Kruskalův algoritmus, keříková struktura Union-Find | + | |
- | | 24. 3.| Stromové datové struktury: binární vyhledávací stromy, AVL-stromy **[L 8]** [[https:// | + | |
- | | 31. 3.| $(a, | + | |
- | | 7. 4.| rekapitulace LLRB, amortizace, úvod do hešování **[L 9.1-9.2; 11.3]** [[https:// | + | |
- | | 14. 4.| Hešování s otevřenou adresací, univerzální hešování **[L 11.3-11.4]**, | + | |
- | https:// | + | |
- | | 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; | + | |
+ | ====== ADS1 Exam / 2022 ====== | ||
+ | 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 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 | ||
- | ===== Zkouška ADS 1 / 2020 ===== | + | 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 |
- | Na zkoušce budou zadány | + | ==== Grading ==== |
- | - Dva příklady na algoritmy či datové struktury z přednášky | + | **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). |
- | - Dvě úlohy podobné těm ze cvičení | + | |
- | === Hodnocení === | + | **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/ |
- | **Na 3** stačí znát definice a algoritmy a nechat se dostrkat k řešení aspoň jedné úlohy | + | **To get a 1** you need to analyze the algorithms |
- | **Na 2** je potřeba umět řešit úlohy s nápovědou, | + | ===== Topics ===== |
- | **Na 1** je potřeba i rozbor algoritmů (správnost a složitost včetně důkazů tvrzení) a umět řešit úlohy víceméně samostatně (ale nápověda typu “tady se hodí použít vyhledávací strom” je na jedničku stále v pořádku). | + | **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. |
- | === Okruhy === | + | |
- | + | * DFS applications: topological sorting, detecting strongly connected components | |
- | **Pozor**, okruhy níže // | + | * Dijkstra’s algorithm |
- | + | * Bellman-Ford’s algorithm | |
- | | + | * Floyd-Warshall’s algorithm (small topic) |
- | * Aplikace | + | * Jarník’s algorithm |
- | * Dijkstrův algoritmus | + | * Borůvka’s algorithm |
- | * Bellman-Fordův algoritmus | + | * Kruskal’s algoritmus + Union-Find |
- | * Floyd-Warshallův algoritmus — půltéma | + | * Binary Search Trees (BSTs) in general |
- | * Jarníkův algoritmus | + | * AVL trees |
- | * Borůvkův algoritmus | + | * $(a,b)$-trees |
- | * Kruskalův algoritmus + Union-Find | + | * Red-black trees – we covered these very briefly, but you should be able to describe the bijection between LLRBs and $(2, |
- | * BVS obecně | + | * Hashing with chaining |
- | * AVL stromy | + | * Hashing with open addressing (warning, I did this at the tutorial; if you don’t understand it, please read JeffE’s notes) |
- | * $(a,b)$-stromy | + | * Universal hashing |
- | * Červeno-černé stromy | + | * Master theorem – analyzing the complexity of Divide & Conquer algorithms using the recursion tree |
- | * Hešování s přihrádkami | + | * Integer multiplication using Karatsuba’s algorithm |
- | * Hešování | + | * MomSelect (finding the $k$-th smallest element in an array in linear time) |
- | * Univerzální hešování | + | * Edit Distance dynamic programming algorithm |
- | * Kuchařková věta, rozbor algoritmu rozděl a panuj pomocí stromu rekurze | + | * Longest Increasing Subsequence dynamic programming algorithm |
- | * Násobení dlouhých čísel pomocí rozděl a panuj; Strassenův algoritmus (idea) | + | * 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) |
- | * 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 | + | |
- | + | ||
- | */ | + | |
teaching/ads12122_lecture.1649856526.txt.gz · Poslední úprava: 2022/04/13 15:28 autor: Martin Koutecky