| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:ads12324_lecture [2024/03/21 22:45] – Martin Koutecky | teaching:ads12324_lecture [2024/05/08 00:26] (aktuální) – Martin Koutecky |
|---|
| | 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]].| | | 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]** | | | 12. 3. | Finish SCC algorithm **[A, Chap 3]**; begin shortest paths: BFS, Dijkstra. **[A, Chap 4]** | |
| | 19. 3. | general relaxation algorithm, start Bellman-Ford **[A, Chap 4]**.| | | 19. 3. | $d$-ary heaps for Dijkstra; general relaxation algorithm, start Bellman-Ford **[A, Chap 4]**.| |
| | 26. 3. | //Plan: Bellman-Ford; Floyd-Warshall for APSP. **[A 4]** //(Also see **[JE 8, 9]** but that's a lot more information than necessary.)// Beginning of Min Spanning Trees: if edge weights distinct, MST is unique. **[A 5]**, **[JE 7]**.) //| | | 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.| |
| | | 23. 4. | Brief mention of amortized analysis: expanding arrays can do $n$ INSERT / DELETE operations in time $O(n)$ (but not each operation is $O(1)$) [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/09-amortize.pdf|JeffE]]. Brief mention of LLRB trees [[https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf|original paper]], [[https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf|slides]], [[https://read.seas.harvard.edu/~kohler/notes/llrb.html|controversy]]. Divide & conquer -- Recursion tree technique, Karatsuba's algorithm for multiplication of $n$-digit numbers in time $n^{\log_2 3}$ **[JE 1]**, specifically [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf|here]]| |
| | | 30. 4. | Master theorem [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf|JE 1]], QuickSelect is fast in expectation, thus QuickSort is fast in expectation [[https://en.wikipedia.org/wiki/Quicksort#Average-case_analysis|Wiki]]| |
| | | 7. 5. | Finding the $k$-th element in $O(n)$ time by the "median of medians" technique **[JE 1]**. Sorting lower bound [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/12-lowerbounds.pdf| JeffE's notes]]. Begin dynamic programming: Longest Increasing Subsequence in $O(n^2)$ time with a table; brief mention that it can be done in $O(n \log n)$ with an enhanced balanced binary search tree [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/03-dynprog.pdf|JE 3]].| |
| | | 14. 5. | //No lecture!//| |
| | | 21. 5. | //Plan: dynamic programming - edit distance, Floyd-Warshall [JE 3], [A 6], specifically [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/03-dynprog.pdf|here]].//| |
| | |
| /* | /* |
| | 16. 3. | Shortest paths: recap of Bellman-Ford; Floyd-Warshall for APSP. **[A 4]** //(Also see **[JE 8, 9]** but that's a lot more information than necessary.)// Beginning of Min Spanning Trees: if edge weights distinct, MST is unique. **[A 5]**, **[JE 7]**.) [[https://stream.cuni.cz/cs/Detail/16775|recording]]| | |
| | 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]]| | | 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]]| | | 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]]| |
