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 to come later.

Useful Resources

[ALG] Algorithm Labyrinth Guide by Mareš and Valla. EXPERIMENTAL: this is a work-in-progress, AI-generated translation of the excellent Czech textbook Průvodce Labyrintem Algoritmů. It may be rough or even wrong (due to translation issues); I'll be working on improving it, especially the parts directly relevant to covered material.
[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