| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:ads12526_lecture [2026/03/28 23:24] – test edit by claude automated task Claude Cowork | teaching:ads12526_lecture [2026/03/30 14:25] (aktuální) – Update lecture 30. 3. and add plan for 6. 4. Claude Cowork |
|---|
| | 16. 3. | binary, $d$-ary, Fibonacci heaps for Dijkstra; general relaxation algorithm, start Bellman-Ford **[ALG 6.1-6.3]**, **[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]**.)| | | 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]**.//| |
| |
| /* | /* |
| | 2. 4. | //(test edit by claude)// | | 2. 4. | |
| | 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]]| | | 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.| | | 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.| |
