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].) |
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.1647425759.txt.gz · Poslední úprava: 2022/03/16 11:15 autor: Martin Koutecky