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. | Line segment intersections slides. Begin reductions, hardness. |
| 9. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. recording (2022), slides, JeffE (more than you asked for). Very good pictures for the reduction 3,3-SAT → 3DM 1, 2, 3, 4, 5; (source (Korean)) |
| 16. 12. | Q&A about 3,3-SAT → 3DM reduction. Classes P, NP; Cook's theorem. slides, JeffE, recording (2022). Dealing with NP-hardness. IndSet is solvable on trees; coloring is solvable on interval graphs. |
| 6. 1. | Plan: Knapsack is solvable in pseudopolynomial time (=when input values are polynomially bounded). Approximation: 2-approximation algorithm for $\Delta$-TSP (on a complete graph and with $\Delta$-inequality). No $\alpha$-approximation for general TSP. Fully polynomial time approximation scheme (FPTAS) for Knapsack (downscaling values). slides 1, slides 2, recording (2022) |
The exam will consist of:
The form of the exam is that you will come, get the question sheet, and work on the answers. Once you are finished with one of the answers, you hand it in, I will read it, point out anything which is missing / incorrect, give you hints if needed, and you can revise it. At some point either you will reach a correct solution, or you won’t want to try to improve it again, or I will feel like I can’t give you any more hints, and then we’ll reach some grade.
To get a 3 it roughly suffices to (operationally!) know definitions and algorithms / data structures and (with hints) finish at least one of the “type 2” tasks (perhaps suboptimally).
To get a 2 you need to be able to solve the tasks with some hints, or find a suboptimal (complexity) algorithm. If we proved some intermediate claims during the lecture, and these are used in the proofs of correctness/complexity, you need to at least know the statements of these claims.
To get a 1 you need to analyze the algorithms (correctness and complexity) including the proofs, and you need to be able to solve the “type 2” tasks mostly independently. (Advice like “try dynamic programming” and similar is still fine though.)
I am extremely annoyed by people trying to cheat at the exam, and if I see anything fishy that you don't satisfactorily explain at the moment, you have failed the exam, you will be reported, and you won't have another chance at taking the exam with me. Don't cheat.
Disclaimer: the topics below are NOT specific instances of “type 1” questions. It is clear that some topics are wider and some narrower. However, if you have a good understanding of all the topics below, you should not be surprised by anything during the exam.
