| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verzePoslední revizeObě strany příští revize |
| teaching:ads12122_lecture [2022/04/20 13:08] – Martin Koutecky | teaching:ads12122_lecture [2022/05/18 14:48] – Martin Koutecky |
|---|
| | 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]]| | | 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]]| | | 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]]| | | 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]]| |
| |
| |
