After the introductory lecture, the course Advanced Algorithms consists of three independent parts, taught by different lecturers: (1) algebraic and number-theoretic algorithms, (2) graph algorithms, and (3) string algorithms. For further information, please refer to the schedule below.
Time & Place
Thursday, 14:45 - 16:15, Room 007 of Science Building Number 7
Grade
You are required to submit at least two of the three assignments (writing lecture notes counts as submitting the solution to an assignment). Note that each assignment may have further requirements itself. The average of the best two of your submissions determines your final grade.
| Date | Title / Contents | Lecturer | Notes |
|---|---|---|---|
| 4/8 | Introduction | Hiroshi Imai | PDF TeX |
| 4/15 | Polynomial Identity Testing, the Schwartz-Zippel Theorem and Edmonds' Theorem (Chapter 7 of RA) | François Le Gall | PDF TeX |
| 4/22 | Fingerprinting and Universal Hashing (Chapters 7 and 8 of RA) | François Le Gall | PDF TeX |
| 5/13 | Number-theoretic algorithms: basics (Chapter 14 of RA) | François Le Gall | PDF TeX |
| 5/20 | Number-theoretic algorithms: primality testing I (Chapter 14 of RA) | François Le Gall | PDF TeX |
| 5/27 | Number-theoretic algorithms: primality testing II (Chapter 14 of RA) | François Le Gall | PDF TeX |
| Assignment 1 | |||
| 6/3 | Graph algorithms: Minimum Cut (Chapter 10.2 of RA) | Christian Sommer | PDF TeX |
| 6/10 | Graph algorithms: All Pairs Shortest Paths (R. Seidel, JCSS 1995 and Chapter 10.1 of RA) | Christian Sommer | PDF TeX |
| 6/17 | Graph algorithms: Permutation Routing, Chernoff Bound(s) (Chapter 4.2 of RA) | Christian Sommer | PDF TeX |
| 6/24 | Graph algorithms: Permutation Routing, Probabilistic Method (Chapter 5.4 of RA) | Christian Sommer | PDF TeX |
| Assignment 2 | |||
| 7/1 | String algorithms: Text searching algorithms | Tetsuo Shibuya | Slides |
| 7/8 | String algorithms: Text indexing algorithms | Tetsuo Shibuya | Slides |
| 7/15 | String algorithms: Text compression algorithms | Tetsuo Shibuya | Slides |
| Assignment 3: on the last slide of the Slides of Lecture 13 | |||