February-March 2014

Here is a related, more math-oriented course taught by Ross J. Kang and Tobias Müller in Fall'13 in Utrecht.

- Stasys Jukna,
*Extremal Combinatorics, with Applications in Computer Science*, 2nd edition, Springer, 2011.

Chapters can also be downloaded from the UvA library.

- [Feb 5] Introduction and some basic counting techniques

Book: Preface/Notation. Chapter 1.1, 1.4, 4.3

Homework (to be handed in Feb 7): Exercises 1.2, 1.5, 1.9, 1.10, 1.12, 1.13 - [Feb 7] More advanced counting

Book: Chapter 1.2, 1.6, 2.6 [only Lovasz-Stein. NB: equation 2.7 should be reversed]

Homework (to be handed in Feb 14): Exercises 1.21, 1.32, 1.33, 2.1 - [Feb 12] The pigeonhole principle

Book: Chapter 4.1, 4.2, 4.4, 4.5, and the lower bound for resolution

Homework (to be handed in Feb 14): Exercises 4.4, 4.5, 4.11, 4.14, 4.16 - [Feb 14] Systems of distinct representatives and algorithms for matching

Book: Chapter 5, except 5.2.1

Homework (to be handed in Feb 21): Exercises 5.1, 5.6, 5.8, 5.9 - [Feb 19] Sunflowers

Book: Chapter 6.1, 6.2.2, 6.3.2

Homework (to be handed in Feb 21): Exercises 6.2, 6.3, 6.6, 6.11, 6.12 - [Feb 21] Chains and antichains

Book: Chapter 8.1, 8.3, 8.6, and Sections 1 and 2 of this application to data structures

Homework (to be handed in Feb 28): Exercises 8.1, 8.4, 8.5, 8.10 - [Feb 26] Blocking sets

Book: Chapter 9.1, 9.2, 9.4

Homework (to be handed in Feb 28): Exercises 9.2, 9.6, 9.7, 9.9 [NB: you need to prove a lower bound of m^2] - [Feb 28] The linear algebra method

Book: Chapter 13.1, 13.3, 13.6

Homework (to be handed in Mar 7): Exercises 13.1, 13.9, 13.10, 13.17 [page 196, line 4: the mu_j indices should be mu_{I_j}, and order the |I_j| from small to large] - [Mar 5] The probabilistic method I

Book: Chapter 3.1, 3.2, 18.1, 18.7

Homework (to be handed in Mar 7): Exercises 3.5, 3.10, 3.11, 3.12 - [Mar 7] The probabilistic method II

Book: Chapter 3.3, 17.3, 18.11, and Section 3 of this application to data structures

Homework (to be handed in Mar 14): Exercises 3.3, 17.2, 17.7, 18.9, 18.14 - [Mar 12] Randomized algorithms, random walks

Book: Chapter 16.1 and 23.1

Homework (to be handed in Mar 14): Exercises 16.2, 16.3, 16.4, 23.1 - [Mar 14] Expander graphs

Book: Chapter 15.1, 15.2 and 23.3

Homework (to be handed in Mar 21): Exercises 15.1, 15.2, 15.4, 15.5 [additonal hint: write the trace of A^2 in two different ways] - [Mar 19] Hereditary sets and matroids

Book: Chapter 10.1, 10.2 and 10.3

Homework (to be handed in Mar 21): Exercises 10.1, 10.10, 10.11, 10.12, 10.13 - [Mar 21] Communication complexity

Instead of the book: this introduction to communication complexity

No homework, but probably one exam-question will be about communication complexity

[Mar 29] final exam 10.30-13.30 in SP A1.06.

NB: this is a *Saturday*, not the earlier-planned Friday (to prevent overlap with another exam)

[Apr 12] re-sit of the exam 10.30-13.30 in SP A1.06.

If you want to practice: here and here are two old exams

Last update of this page: April 8, 2014.