teaching:ads12324_lecture
Toto je starší verze dokumentu!
Algorithms and Data Structures I 2023/24 -- Lecture
I teach Algorithms and Data Structures I (NTIN060) every Tuesday at 12:20 at S9 (Malá strana). I have taught this class last year and there are some (somewhat problematic) recordings from then (see the link).
I also teach a tutorial for this class on Monday at 15:40, and another one is taught on Tuesday at 17:20 by Todor Antić. Both tutorials will cover the same content and have the same criteria for obtaining credit.
If you want to talk to me, schedule a meeting with me.
You can 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] |
---|---|
19. 2. | The Random Access Machine (RAM) model of computation, instruction cost (unit, logarithmic, relative logarithmic) [A Chapter 0], Wiki: Random Access Machine, Big-Oh notation ($\mathcal{O}, \Omega, \Theta$) |
27. 2. | Graph problems, DFS: identifying connected components, pre- and post-orderings, cycle detection. [A, up to 3.3.2] |
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: notes, demo. |
12. 3. | Finish SCC algorithm [A, Chap 3]; begin shortest paths: BFS, Dijkstra. [A, Chap 4] |
19. 3. | $d$-ary heaps for Dijkstra; general relaxation algorithm, start Bellman-Ford [A, Chap 4]. |
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 (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. slides from U of Washington). OneNote notes. AVL tree rebalancing. Possible resources for AVL trees: 1, 2, 3 |
16. 4. | $(a,b)$-trees 1, 2, hashing hashing notes from Jeff E. In tutorials: we showed a construction of a $1$-universal family of hashing functions, see 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)$) JeffE. Brief mention of LLRB trees original paper, slides, controversy. Divide & conquer – Recursion tree technique, Karatsuba's algorithm for multiplication of $n$-digit numbers in time $n^{\log_2 3}$ [JE 1], specifically here |
30. 4. | Plan: Master theorem, finding the median (or any $k$-th element) in $O(n)$ time by the „median of medians“ technique [JE 1], quicksort in the average case |
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/ads12324_lecture.1714082809.txt.gz · Poslední úprava: 2024/04/26 00:06 autor: Martin Koutecky