Rozdíly

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

--- teaching:ads12526_lecture [2026/02/17 23:42] – Martin Koutecky
+++ teaching:ads12526_lecture [2026/03/30 14:25] (aktuální) – Update lecture 30. 3. and add plan for 6. 4. Claude Cowork
@@ Řádek 11: / Řádek 11: @@
 ^ data ^ what was taught [resources] ^
 | 16. 2.| The Random Access Machine (RAM) model of computation, instruction cost (unit, logarithmic, relative logarithmic) **[ALG 2]**, **[A 0]**, **[[https://en.wikipedia.org/wiki/Random-access_machine#Formal_definition|Wiki: Random Access Machine]]**, Big-Oh notation ($\mathcal{O}, \Omega, \Theta$)|
-| 23. 2. |//Plan: Graph problems, DFS: identifying connected components, pre- and post-orderings, cycle detection. **[A, up to 3.3.2]**//|
+| 23. 2. |Graph problems, DFS: in- and out-orderings, edge classification, cycle detection. **[ALG 5.6]**, **[A, up to 3.3.2]**, **Also learn** the $\mathcal{O}(n+m)$ algorithm to find all bridges of an undirected graph **[ALG 5.7]**, [[https://cp-algorithms.com/graph/bridge-searching.html|notes]]|
+| 2. 3 | DFS: topological ordering, detecting strongly connected components. **[ALG 5.8-5.9]**,  **[A, remainder of Chap 3]**. |
+| 9. 3 | Finish SCC algorithm **[ALG 5.9]**, **[A, Chap 3]**; begin shortest paths: BFS **[ALG 5.2]**, Dijkstra **[ALG 6.0-6.2]**, **[A, Chap 4]**|
+| 16. 3. | binary, $d$-ary, Fibonacci heaps for Dijkstra; general relaxation algorithm, start Bellman-Ford **[ALG 6.1-6.3]**, **[A, Chap 4]**.|
+| 23. 3. | Bellman-Ford **[ALG 6.3]**, **[A 4]** //(Also see **[JE 8, 9]** but that's a lot more information than necessary.)// Start Min Spanning Trees: cut lemma, if edge weights distinct, MST is unique; Jarník's algorithm; Borůvka's algorithm **[ALG 7-7.3]**, **[A 5]**, **[JE 7]**.)|
+| 30. 3. | Kruskal's algorithm; Union-Find problem and data structure via forests ("bushes"), $\mathcal{O}(\log n)$ Union and Find **[ALG 7.4]**, **[A 5.1.4]**. Start data structures: Binary Search Trees; perfectly balanced BSTs have depth $\mathcal{O}(\log n)$ **[ALG 8.1]** ([[https://ksvi.mff.cuni.cz/~dingle/2021-2/algs/notes_10.html|intro to Algs notes]])|
+| 6. 4. | //Plan: Constructing a perfectly balanced BST from a sorted array in $\mathcal{O}(n)$ time; perfectly balanced BSTs cannot be maintained efficiently. AVL trees, start $(a,b)$-trees **[ALG 8.2-8.3]**.//|
 /*
-| 27. 2. | Graph problems, DFS: identifying connected components, pre- and post-orderings, cycle detection. **[A, up to 3.3.2]**|
+| 2. 4. |
-| 5. 3. | DFS: topological ordering, detecting strongly connected components. **[A, remainder of Chap 3]**. **Also learn** the $\mathcal{O}(n+m)$ algorithm to find all bridges of an undirected graph: [[https://cp-algorithms.com/graph/bridge-searching.html|notes]], [[https://syga.app/#/algorithm/detail/syga/dfs-bridges/latest|demo]].|
-| 12. 3. | Finish SCC algorithm **[A, Chap 3]**; begin shortest paths: BFS, Dijkstra. **[A, Chap 4]** |
-| 19. 3. | $d$-ary heaps for Dijkstra; general relaxation algorithm, start Bellman-Ford **[A, Chap 4]**.|
-| 26. 3. | Bellman-Ford **[A 4]** //(Also see **[JE 8, 9]** but that's a lot more information than necessary.)// Beginning of Min Spanning Trees: cut lemma, if edge weights distinct, MST is unique; Jarník's algorithm; Borůvka's algorithm **[A 5]**, **[JE 7]**.)|
-| 2. 4. | Finish Borůvka's algorithm; Kruskal's algorithm for MSTs, Union-Find problem and data structure. **[A 5.1.4]**. Intro to Data structures. Binary Search Trees ([[https://ksvi.mff.cuni.cz/~dingle/2021-2/algs/notes_10.html|intro to Algs notes]]) |
 | 9. 4. | Perfectly balanced trees (//balancing turns out to be too expensive, this is a dead-end//); 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}}**. AVL tree rebalancing. 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]]|
 | 16. 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]], hashing [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-hashing.pdf|hashing notes from Jeff E]]. **In tutorials: we showed a construction of a $1$-universal family of hashing functions, see [[https://research.koutecky.name/db/_media/teaching:ads12324:09-cv.pdf|here]]**. This theorem may appear at the exam.|