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. [A 1], specifically here.

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