I teach Algorithms and Data Structures I (NTIN060) every Monday at 12:20 at N1 (IMPAKT). I have taught this class two and three years ago and there are some (somewhat problematic) recordings from then (see the links).
There are three tutorials for the class: two taught by Jamie Fravel, and one by Petr Kučera. All tutorials will cover the same content and have the very similar criteria for obtaining credit, though some variations will exist.
The best way to reach me is on discord: my handle is mkoutecky and there's a channel for ADS1 at the MFF-U Discord Server (invite link).
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] |
|---|---|
| 16. 2. | The Random Access Machine (RAM) model of computation, instruction cost (unit, logarithmic, relative logarithmic) [ALG 2], [A 0], Wiki: Random Access Machine, Big-Oh notation ($\mathcal{O}, \Omega, \Theta$) |
| 23. 2. | Graph problems, DFS: in- and out-orderings, edge classification, cycle detection. [ALG 5.6], [A, up to 3.3.2], Also learn the $\mathcal{O}(n+m)$ algorithm to find all bridges of an undirected graph [ALG 5.7], notes |
| 2. 3 | DFS: topological ordering, detecting strongly connected components. [ALG 5.8-5.9], [A, remainder of Chap 3]. |
| 9. 3 | Finish SCC algorithm [ALG 5.9], [A, Chap 3]; begin shortest paths: BFS [ALG 5.2], Dijkstra [ALG 6.0-6.2], [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].) |
| 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] (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]. |