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