Rozdíly

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

--- teaching:ads12122_lecture [2022/03/30 17:50] – Martin Koutecky
+++ teaching:ads12122_lecture [2022/05/23 11:45] (aktuální) – exam Martin Koutecky
@@ Řádek 15: / Řádek 15: @@
 | 23. 3. | Minimum Spanning Trees: Cut property (the MST contains every safe edge), Borůvka, Jarník, Kruskal **[JE 7]**, Union-Find data structure **[A 5.1.4]**. [[https://stream.cuni.cz/cs/Detail/16842|recording]]|
 | 30. 3. | Union-Find Data structure **[A 5.1.4]**; Binary Search Trees ([[https://ksvi.mff.cuni.cz/~dingle/2021-2/algs/notes_10.html|intro to Algs notes]]), perfect balancing too expensive; depth-balanced trees = AVL trees. [[https://courses.cs.washington.edu/courses/cse373/19su/files/lectures/slides/lecture09.pdf|slides from U of Washington]]). **{{ :teaching:ads12122:ads_bsts.pdf |OneNote notes}}**. [[https://stream.cuni.cz/cs/Detail/16918|recording]]|
+| 6. 4. | AVL tree rebalancing, intro to $(a,b)$-trees. [[https://stream.cuni.cz/cs/Detail/16972|recording]]. Possible resources for AVL trees: [[https://www.programiz.com/dsa/avl-tree|1]], [[http://gtu-paper-solution.com/Paper-Solution/DataStructure-2130702/AVL%20Trees/Summer-2019/Question-4-c-OR|2]], [[https://courses.cs.washington.edu/courses/cse373/19su/files/lectures/slides/lecture09.pdf|3]]|
+| 13. 4. | $(a,b)$-trees [[https://cs.lmu.edu/~ray/notes/abtrees/|1]], [[http://www14.in.tum.de/lehre/2016WS/ea/split/sub-ab-trees-single.pdf|2]], LLRB trees [[https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf|original paper]], [[https://sedgewick.io/talks/?pdfjs_id=1281&_wpnonce=effd5be684#zoom=auto|slides]], [[https://read.seas.harvard.edu/~kohler/notes/llrb.html|controversy]]. [[https://stream.cuni.cz/cs/Detail/17028|recording]]|
+| 20. 4. | Amortized analysis, hashing [[https://stream.cuni.cz/cs/Detail/17063|recording]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-hashing.pdf|hashing notes from Jeff E]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/09-amortize.pdf|amortized analysis notes by Jeff E]]|
+| 27. 4. | Universal, perfect hashing [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-hashing.pdf|hashing notes from Jeff E]], open addressing will be done at tutorial. [[https://stream.cuni.cz/cs/Detail/17230|recording]]|
+| 4. 5. | Divide & conquer -- Karatsuba's algorithm for multiplication of $n$-digit numbers in time $n^{\log_2 3}$, finding the median (or any $k$-th element) in $O(n)$ time by the "median of median" technique. [JE 1], specifically [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf|here]]. [[https://stream.cuni.cz/cs/Detail/17289|recording]]|
+| 18. 5. | Sorting lower bound [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/12-lowerbounds.pdf| JeffE's notes]], Dynamic programming [JE 3], [A 6], specifically [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/03-dynprog.pdf|here]]. [[https://stream.cuni.cz/cs/Detail/17423|recording]]|
 {{page>teaching:bits:resources_ads1}}
-/*
+{{ :teaching:ads12122:exam2122.pdf | Exam topics and format (PDF).}}
-| 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í; detekce komponent silné souvislosti v lineárním čase; úvod do nejkratších cest **[L 5.7-6.1]**|
-| 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  **[L 7.1-7.4]**, [[https://stream.cuni.cz/cs/Detail/3329|video přednášky]], {{ :teaching:ads11920:kostry_prednaska.pdf |"zápis" z přednášky}}|
-| 24. 3.| Stromové datové struktury: binární vyhledávací stromy, AVL-stromy **[L 8]** [[https://stream.cuni.cz/cs/Detail/3507|video přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoBr1koI1loAthyZ2kTeyjsRQ?e=bkanMC|zápis z přednášky (OneNote)]]|
-| 31. 3.| $(a,b)$-stromy, červeno-černé stromy **[L 8]**[[https://stream.cuni.cz/cs/Detail/3779|video přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoBr1koI1loAthyZ2kTeyjsRQ?e=bkanMC|zápis z přednášky (OneNote)]]|
-| 7. 4.| rekapitulace LLRB, amortizace, úvod do hešování **[L 9.1-9.2; 11.3]** [[https://stream.cuni.cz/cs/Detail/4070|video přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoBr1koI1loAthyZ2kTeyjsRQ?e=bkanMC|zápis z přednášky (OneNote)]]|
-| 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?e=D4S5Fv|zápis z přednášky (OneNote)]]|
-| 21. 4.| Rozděl a panuj - úvod, kuchařková věta, násobení dlouhých čísel **[L 10]**, [[https://stream.cuni.cz/cs/Detail/4569|video z přednášky]] [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoB3OsgQAyUXxTRt5BeNqVVWw?e=D4S5Fv|zápis z přednášky (OneNote)]]|
-| 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://stream.cuni.cz/cs/Detail/4766|video z přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoB3OsgQAyUXxTRt5BeNqVVWw?e=D4S5Fv|zápis z přednášky (OneNote)]]|
-| 5. 5.| Dynamické programování - Editační vzdálenost; dolní odhady na třídění; quicksort v průměrném případě [[https://stream.cuni.cz/cs/Detail/4937|video z přednášky]], [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoB3OsgQAyUXxTRt5BeNqVVWw?e=D4S5Fv|zápis z přednášky (OneNote)]] **[L 12.3, 3.3, 11.2]**|
+====== ADS1 Exam / 2022 ======
+The exam will consist of:
-{{ :teaching:zkouska.pdf |Okruhy, průběh zkoušky. (PDF)}}
+  - 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 (need to understand how it works internally to be able to adapt it appropriately)
-===== 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 / 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 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/complexity, you need to at least know the statements of these claims.
-**Na 3** stačí znát definice a algoritmy a nechat se dostrkat k řešení aspoň jedné úlohy (nebo ji vyřešit neefektivně).
+**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.)
-**Na 2** je potřeba umět řešit úlohy s nápovědou, případně na ně najít méně efektivní algoritmus. Pokud jsme na přednášce o algoritmech vyslovovali nějaká tvrzení, je třeba znát aspoň zhruba jejich znění.
+===== 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 ===
+  * BFS, DFS and their edge classifications
+  * DFS applications: topological sorting, detecting strongly connected components
-**Pozor**, okruhy níže //nepředstavují// konkrétní příklady na algoritmy či datové struktury. Je zřejmé, že některé okruhy níže jsou širší a některé užší. Pokud ale budete mít přehled o všech tématech níže, nic na zkoušce by vás nemělo zaskočit.
+  * Dijkstra’s algorithm
+  * Bellman-Ford’s algorithm
-  * BFS, DFS a jejich klasifikace hran
+  * Floyd-Warshall’s algorithm (small topic)
-  * Aplikace DFS: topologické třídění, detekce SSK
+  * Jarník’s algorithm
-  * Dijkstrův algoritmus
+  * Borůvka’s algorithm
-  * Bellman-Fordův algoritmus
+  * Kruskal’s algoritmus + Union-Find data structure using trees
-  * 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 pomocí keříků
+  * Red-black trees – we covered these very briefly, but you should be able to describe the bijection between LLRBs and $(2,4)$-trees
-  * 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í s otevřenou adresací
+  * 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
-*/