Algorithms and Data Structures II
In the winter semester 2017/2018, 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 Friday from 9:00 in room S3.
Classes (exercises) are on Tuesdays from 12:20 in room S10. They are taught by Petr Kučera. Czech-speaking students can also select any classes of the Czech version of the course, but they are likely to be differences in the order of topics taught.
Syllabus
| date | topic |
|---|---|
| 6. 10. | Searching in text: notation on strings, naïve algorithms, the KMP (Knuth, Morris, Pratt) algorithm and its analysis. |
| 13. 10. | Text searching continued: Aho-Corasick algorithm searching for multiple strings simultaneously. Using rolling hash functions: the Rabin-Karp algorithm. |
| 20. 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. |
| 27. 10. | Network flows: An equivalent definition of a flow. Layered networks and blocking flows. The Dinitz's algorithm. |
| 3. 11. | Network flows: The Goldberg's algorithm (preflow push). |
| 10. 11. | Network flows: The rest of analysis of Goldberg's algorithm. Introduction to boolean circuits. |
| 17. 11. | Enjoy the holiday. |
| 24. 11. | Parallel programming on boolean circuits: binary addition. Comparator networks and bitonic sorting. |
| 1. 12. | Multiplication of polynomials. Complex roots of unity. |
| 8. 12. | Fast Fourier transform and its inverse. FFT circuits, non-recursive FFT. Algebraic interpretations. |
| 15. 12. | Decision problems and reductions between them: SAT, 3-SAT, independent set. |
| 22. 12. | More reductions: clique, 3,3-SAT, 3D-matching. Complexity classes P and NP, NP-hard and NP-complete problems and their basic properties. Cook's theorem: SAT is NP-complete (proof omitted). |
| 5. 1. | Geometric algorithms in the plane: convex hull, line segment intersection, Voronoi diagrams, point location and persistent search trees. |
| 12. 1. | 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. |
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 need to have course credit from exercise classes before you take the exam.
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.
Recommended reading
- 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)
- Other materials in Czech language