Discrete Mathematics and Computational Structures

Summer 2010

Administrivia

Instructor: Yoshio Okamoto
Time: Monday, 10:40-12:10
Place: W832 Lecture Room, West 8 Bldg, Ookayama Campus, Tokyo Institute of Technology

Topic

Extremal combinatorics and its applications in computer science

Online Discussion Forum (Japanese)

Visit the wiki page of the course.

Slides and Exercises

Slides in the lectures and the sheet of exercises will be available from the OCW (Tokyo Tech OpenCourseWare).

Tentative Schedule

Apr 12, 2010: Lecture 1 (Introduction, Counting Basics)
Apr 19, 2010: Lecture 2 (The Pigeonhole Principle)
Apr 26, 2010: Lecture 3 (Coloringd)
May 3, 2010: Constitution Memorial Day
May 10, 2010: Lecture 4 (Sunflowers)
May 17, 2010: Lecture 5 (Blocking Sets and Duality)
May 24, 2010: Lecture 6 (The Switching Lemma)
May 31, 2010: Lecture 7 (Density and Universality)
June 7, 2010: Lecture 8 (Witness Sets and Isolation)
June 14, 2010: Lecture 9 (Designs)
June 21, 2010: Lecture 10 (The Linear Algebra Method Basics)
June 28, 2010: Lecture 11 (Orthogonality and Rank Arguments)
July 5, 2010: No class
July 12, 2010: Lecture 12 (Span Programs)
July 19, 2010: Marine Day
July 22 (Thu), 2010: No class

okamotoy@uec.ac.jp