Rozdíly

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

--- teaching:ads12526_lecture [2026/03/23 22:29] – 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 16: / Řádek 16: @@
 | 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. | //Plan: Kruskal's algorithm for MSTs, Union-Find problem and data structure. **[ALG 7.4]**, **[A 5.1.4]**. Intro to Data structures. Binary Search Trees **[ALG 8]** ([[https://ksvi.mff.cuni.cz/~dingle/2021-2/algs/notes_10.html|intro to Algs notes]])//|
+| 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]**.//|
 /*