# Advanced Algorithms (Summer 2010)

Computer Science Department, The University of Tokyo

## Course Overview

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

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.

## Material

Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan

## Schedule

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

## Scribe Notes

Writing scribe notes using LaTeX is technically not difficult. If you are not familiar with LaTeX, you can find hundreds of introductions online, for example this not so short introduction. Please use this LaTeX Template for your scribe notes. You may also use the scribe notes of the first lecture as a starting point. In case you're looking for a special LaTeX symbol (such as a math symbol), Detexify may be a very helpful tool.