4810-1163 Advanced Algorithms 先端アルゴリズム論 (Summer 2014)

Thursday 2:50–4:20 pm, Science Building 7, Room 007 (despite what the printed timetable says)

Instructors: H. Imai, A. Kawamura, F. Le Gall, T. Shibuya


Introduction (Imai) April 3, 10

Part 1: Algebraic and number-theoretic algorithms (Le Gall)

Part 2: Probabilistic methods, random walks, and derandomization (Kawamura) May 22, 29, June 5, 12

Part 3: String algorithms (Shibuya) June 19, 26, July 3, 10


Submit two of the three assignments (in English or Japanese) by Thursday, July 24, 2014 to the “assignments” box (and not the postboxes of the lecturers) in front of the department office 103 on the ground floor of Science Building 7 (note that the building closes at 6 pm). Please prepare your two submissions separately and indicate the name of the corresponding lecturer on the front pages.


R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
R. Moser and G. Tardos, A constructive proof of the general Lovász Local Lemma, Journal of the ACM 57(2), Article 11, 2010.