# Applied Discrete Mathematics

Time: Monday 8:30-10:00 and Thursday 16:30-18:00

#### Some links:

Webpage of last year's course

Webpage of course containing basics that are required to know

Lovász: Combinatorial Problems and Exercises - good to build up problem solving skills.

Matouek: Thirty-three Miniatures: Mathematical and Algorithmic Applications of
Linear Algebra - we will cover some chapters from here.

#### Topics covered:

11 February: Warm-up exercises appdm1.pdf

15 February: Turán's theorem

18 February: Exercises appdm2.pdf

22 February: Bentley-Ottmann algorithm

25 February: Exercises appdm3.pdf

1 March: Fortune's algorithm

4 March: Stable matchings + Exercises appdm4.pdf

8 March: Intersection of hafplanes and LP in RND linear time

18 March: Exercises appdm5.pdf

22 March: First moment method: Ramsey theory, and large girth and chromatic number

25 March: Exercises appdm6.pdf

29 March: Second moment method: Subgraphs appearing in G(n,p)

8 April: Exercises appdm7.pdf

12 April: Fast perfect matching testing

15 April: Exercises appdm8.pdf

19 April: Number of perfect matching: Kasteleyn signings

22 April: Exercises appdm9.pdf

26 April: Local algorithm for 3-coloring a cycle

29 April: Exercises appdm10.pdf

3 May: Spectral graph theory, largest eigenvalue

10 May: Spectral graph theory, second largest eigenvalue

13 May: Exercises appdm11.pdf