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 |