Algorithms and Data Structures II
In the winter semester 2018/2019, I teach the English version of the basic course on Algorithms and Data Structures II [NTIN061]. It is primarily intended for students of the English study programs, but everybody is welcome.
The lectures are held on every Monday from 10:40 in room S4.
Classes (exercises) are on Mondays from 15:40 in room S11. They are taught by Matej Lieskovský. Czech-speaking students can also select any classes of the Czech version of the course — we will try to keep both versions synchronized.
If you want to consult anything, please write an e-mail to mares+ads@kam.mff.cuni.cz and we will discuss possibilities.
Syllabus
| date | topic |
|---|---|
| 1. 10. | Searching in text: notation on strings, naïve algorithms, the KMP (Knuth, Morris, Pratt) algorithm and its analysis. |
| 8. 10. | Text searching continued: Aho-Corasick algorithm searching for multiple strings simultaneously. Using rolling hash functions: the Rabin-Karp algorithm. |
| 15. 10. | Network flows: Basic definitions and theorems on networks and flows. The Ford-Fulkerson algorithm, proof of its correcntess using cuts. Equality of maximum flow and minimum cut. Integer networks and integer flows. Reducing bipartite matching to integer flow. |
| 22. 10. | Network flows: An equivalent definition of a flow. Layered networks and blocking flows. The Dinitz's algorithm. |
| 29. 10. | Network flows: The Goldberg's algorithm (preflow push) and its analysis. Simulation: uniform path, bottleneck path, maximum height rule (source code). |
| 5. 11. | Network flows: Goldberg's algorithm with the highest vertex rule. Multiplication of polynomials. A review of complex numbers. |
| 12. 11. | Complex roots of unity. Fast Fourier transform and its inverse. FFT circuits, non-recursive FFT. Remarks on FFT (slides): algebraic interpretation, spectral analysis, signal processing. |
| 19. 11. | Parallel programming on boolean circuits: binary addition. Introduction to comparator networks. |
| 26. 11. | Comparator networks and bitonic sorting. Decision problems and reductions between them: SAT and 3-SAT. |
| 3. 12. | More reductions: independent set, clique, 3,3-SAT, 3D-matching. |
| 10. 12. | Complexity classes P and NP, NP-hard and NP-complete problems and their basic properties. Cook's theorem: SAT is NP-complete (proof sketched). |
| 17. 12. | Fighting hard problems. Special cases: independent set in trees, coloring of interval graphs, pseudopolynomial algorithm for knapsack. Approximation algorithms: traveling salesman in a finite metric space (2-approximation), approximation scheme for knapsack. |
| 7. 1. | Geometric algorithms in the plane: convex hull, line segment intersection. Remarks on Voronoi diagrams, point location, and persistent search trees. |
Exams
Exam dates are listed in SIS, please sign up there. If no date suits you, let me know and we can arrange another one. If you want to consult anything before the exam, feel free to ask.
You are expected to know the theory presented at the lectures and to be able to use it for solving algorithmic problems, similar to those from the classes. The necessary (but generally not sufficient) condition of passing the exam is knowledge and understanding of all definitions and algorithms from the syllabus.
Course credit and exam are both required, but neither is a prerequisite for the other.
Recommended reading and other links
- Goldberg's algorithm – an English translation of a chapter from our book.
- Dasgupta, Papadimitriou, Vazirani: Algorithms (a beautiful books on algorithms covering the most of our lecture, available online)
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd or later edition), Mc Graw Hill 2001
- Matoušek, Nešetřil: Invitation to Discrete Mathematics, Oxford University Press. (background in combinatorics and graph theory)
- Last year's lecture
- Other materials in Czech language