Toto je starší verze dokumentu!

Algorithms and Data Structures II 2024/25 -- Lecture

I teach Algorithms and Data Structures II (NTIN061) every Monday at 15:40 at S3 (Malá strana).

If you want to talk to me, send me an email at koutecky+ads2@iuuk.mff.cuni.cz and/or include the text [ADS2] in the email subject, or message me on discord etc. We will then figure out a time and place (physical, zoom, etc.) to meet.

data	what was taught [resources]
30. 9.	Plan: String searching: Knuth-Morris-Pratt algorithm. JeffE's notes, 7.1, 7.4-7.6
7. 10.	String searching: Finished KMP, Aho-Corasick JeffE's notes, 7.2, reference for AC: slides
14. 10.	Rabin-Karp JeffE's notes, 7.3, Network flows intro, Ford-Fulkerson's algorithm. JeffE's notes, 10.1-10.4
21. 10.	Plan: Correctness of Ford-Fulkerson's algorithm JeffE's notes, 10.1-10.4. Dinic's algorithm slides of Honza Hubička, CP-algorithms, NetworkX notebook.
28. 10.	No lecture: Czechoslovak Independence Day
4. 11.	Finish analysis of Dinic. Goldberg's push-relabel algorithm; slides, notes
11. 11.	Multiplying polynomials quickly: FFT (Fast Fourier Transform). slides 1 2, JeffE's notes
18. 11.	Finish FFT algorithm. More notes on FFT. Begin parallel algorithms: fast addition. slides: 1, ; notes for addition (6.1)
25. 11.	Cancelled; will be replaced Friday 29. 11. Plan: Parallel sorting. slides, more slides. Geometric algorithms: convex hull, line segment intersections slides, [CLRS 33.1-33.3]
2. 12.	Plan: line segment intersections slides. Begin reductions, hardness.

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

Notes from Andrej Perković (100MB file) (no guarantee of correctness, email him if you find bugs: arachneen_octogone.0c@icloud.com)