Toto je starší verze dokumentu!

Algorithms and Data Structures II 2022/23 -- Lecture

I teach Algorithms and Data Structures II (NTIN061) every Wednesday at 10:40 at S5 (Malá strana).

If you want to talk to me, you're welcome in my office S326 at Malá Strana, but agree with me on a time to meet first. You can also e-mail me at koutecky+ads2@iuuk.mff.cuni.cz and/or include the text [ADS2] in the email subject.

data	what was taught [resources]
5. 10.	String searching: Knuth-Morris-Pratt algorithm. JeffE's notes, 7.1, 7.4-7.6
12. 10.	String searching: Aho-Corasick, Rabin-Karp JeffE's notes, 7.2-7.3, reference for AC: slides
19. 10.	Finished Rabin-Karp analysis. Network flows intro, Ford-Fulkerson's algorithm. JeffE's notes, 10.1-10.4, recording
26. 10.	Finished Ford-Fulkerson, Dinic's algorithm slides of Honza Hubička, CP-algorithms, NetworkX notebook, recording
2. 11.	Goldberg's push-relabel algorithm recording, slides, notes
9. 11.	Dean's sport day – no class
16. 11.	Parallel algorithms: fast addition, fast sorting. slides: 1, 2, recording; more slides for sorting; notes for addition (6.1)
23. 11.	Design of a comparator (see slides above). Geometric algorithms: convex hull, line segment intersections slides; sorry, no recording. [CLRS 33.1-33.3]
30. 11.	Multiplying polynomials quickly: FFT (Fast Fourier Transform). slides 1 2, JeffE's notes, recording
7. 12.	Finish FFT, begin reductions. recording
14. 12.	Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. recording, slides, JeffE (more than you asked for)
21. 12.	3,3-SAT reduces to 3DM. Classes P, NP; Cook's theorem. slides, JeffE, recording

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