Combinatorics in Computer Science (Fall 2022)
General Information
Instructor: Chihao Zhang

Time:
Thursday
12:55  15:40

Location: 下院113

Office Hour:
Monday
7:00pm  10:00pm
School of Software (软件学院) 14022

References
Combinatorics: A Guided Tour; David Mazur.
Concrete Mathematics; Ronald Graham, Donald Knuth, Oren Patashnik.
The Probabilistic Method; Noga Alon, Joel Spencer.
A Course in Combinatorics; Jacobus H. van Lint, Richard Wilson.
News
Lecture Notes
[Dec 31][notes] Proof of Cheeger's inequality, Kirchoff's Thoerem, Cayley's Formula Revisted
[Dec 22][notes] Reversible Markov Chains, Cheeger's Inequality
[Dec 15][notes] More Spectral Graph Theory, Sensitivity Conjecture
[Dec 08][notes] Spectral Graph Theory, Cauchy Interlacing Theorem
[Dec 01][notes] Algorithmic Lovász Local Lemma, MoserTardos Algorithm
[Nov 30][notes] Lovász Local Lemma
[Nov 24][notes] More Examples on Alteration, Second Moment Method
[Nov 17][notes] Linear Programming Rounding, Semidefinite Programming, MaxCut
[Nov 10][notes] The Probabilistic Method, Derandomization by Conditional Expectations
[Nov 03][notes] Algorithmic Zeta/Möbius Transformation, Fast Subset Convolution
[Oct 20][notes] Sperner's Theorem, Möbius Inversion
[Oct 13][notes] Partially Ordered Sets, Dilworth, König, Hall
[Oct 09][notes] Generating Functions (cont'd)
[Sep 29][notes] Ordinary Generating Functions, Solving Recurrences
[Sep 22][notes] Twelvefold Ways, Principle of InclusionExclusion
[Sep 15][notes] Introduction to the Course, Basic Counting Techniques