teaching:ads12122_lecture
Toto je starší verze dokumentu!
Algorithms and Data Structures I 2021/22 -- Lecture
I teach Algorithms and Data Structures I (NTIN060) every Wednesday at 9:00 at N2 (Troja/IMPAKT).
If you want to talk to me, you're welcome in my office S326 at Malá Strana.
You can also e-mail me at koutecky+ads1@iuuk.mff.cuni.cz
and/or include the text [ADS1]
in the email subject.
data | what was taught [resources] |
---|---|
17. 2. | Richest subsequence. Attempts at defining an algorithm. Von Neumann's computational model, Big-Oh notation ($\mathcal{O}, \mathcal{o}, \Omega, \omega$), the RAM (Random Access Machine) model [A Chapter 0], Wiki: Random Access Machine, recording |
24. 2. | Why graphs problems, DFS: identifying connected components, pre- and post-orderings, cycle detection. [A, up to 3.3.2] recording |
2. 3. | DFS: topological ordering, detecting strongly connected components. [A, remainder of Chap 3], very brief intro to BFS [A, beginning of Chap 4]. recording |
9. 3. | Shortest paths: BFS, Dijkstra, general relaxation algorithm, Bellman-Ford, detecting negative cycles. [A, Chap 4], recording. |
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].) 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]. recording |
30. 3. | Union-Find Data structure [A 5.1.4]; Binary Search Trees (intro to Algs notes), perfect balancing too expensive; depth-balanced trees = AVL trees. slides from U of Washington). OneNote notes. recording |
6. 4. | AVL tree rebalancing, intro to $(a,b)$-trees. recording. Possible resources for AVL trees: 1, 2, 3 |
13. 4. | $(a,b)$-trees 1, 2, LLRB trees original paper, slides, controversy. recording |
20. 4. | Amortized analysis, hashing recording, hashing notes from Jeff E, amortized analysis notes by Jeff E |
27. 4. | Universal, perfect hashing hashing notes from Jeff E, open addressing will be done at tutorial. 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 here. recording |
18. 5. |
Useful Resources
- [A] Algorithms by Dasgupta, Papadimitriou, and Vazirani
- [JE] Algorithms by Jeff Erickson (the page contains various PDFs suitable for screen, printing etc.)
- [CLRS] Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. Find it on libgen
teaching/ads12122_lecture.1652878066.txt.gz · Poslední úprava: 2022/05/18 14:47 autor: Martin Koutecky