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 (软件学院) 1402-2

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, Moser-Tardos Algorithm
[Nov 30][notes] Lovász Local Lemma
[Nov 24][notes] More Examples on Alteration, Second Moment Method
[Nov 17][notes] Linear Programming Rounding, Semi-definite 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 Inclusion-Exclusion
[Sep 15][notes] Introduction to the Course, Basic Counting Techniques