BBM 403 - Combinatorics and Graph Theory (Fall 2020)

ozkahya-at-cs.hacettepe.edu.tr
218
+90 312 297 7193/124

Mathematics for Computer Science, Eric Lehman, Tom Leighton, and Albert Meyer 2018 (available online)
Discrete Mathematics and Its Applications, 7th Edition, Kenneth H. Rosen.
Extremal Combinatorics with Applications in Computer Science, by Stasys Jukna. (electronically available at our library)
Graph Theory (online available), by Reinhard Diestel.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Michael Mitzenmacher and Eli Upfal.
Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan.

Email to arrange an appointment and also use Piazza for quick course related questions. Please enroll by following the link https://piazza.com/hacettepe.edu.tr/fall2019/bbm403

Date	Topic	Reading: (AZ), (KR), (SJ), (MU) and Exercises
Oct. 7 - 11	Counting I: The Binomial Theorem, Double Counting, Jensen's Inequality, The Averaging Principle	SJ: Chapter 1, AZ: pg. 144 Exercises (SJ: Chapter 1): 1-7, 10, 12
Oct. 14 - 18	Counting II: , The Inclusion-Exclusion Principle, Pigeonhole Principle	SJ: Chapters 1, 4 KR: Chap. 7.5-7.6, AZ: pg. 139-140
Oct. 21 - 25	The Probabilistic Method	MU: Chap. 1-2 SJ: Chapter 2
Oct. 28 - Nov. 1	Maximum Matchings, Stable Matchings	SJ: Chap. 5, Slides 1, 2
Nov. 4 - Nov. 8
Nov. 11 - Nov. 15	Moments and Deviations: Calculating mean, Markov's inequality, Chebychev's inequality	MU: Chap. 3
Nov. 18 - Nov. 22	Midterm Exam
Nov. 25 - Nov. 29	Tail Inequalities, Chernoff Bounds	MU: Chap. 4
Dec. 2 - Dec. 6	Some properties of random permutations Balls in Bins, Birthday Paradox	MU: Chap. 5.1-4
Dec. 9 - Dec. 13	Balls and Bins, Poisson Approximation, Hashing	MU: Chap. 5.5-6
Dec. 16 - Dec. 20	Probabilistic Method: The Expectation Method Derandomization Using Conditional Expectations	MU: Chap. 6.2-4
Dec. 23 - Dec. 27	The Second Method Probabilistic Method: Lovasz local lemma	MU: Chap. 6.5-7
Dec. 30 - Jan. 3	Markov Chains	MU: Chap. 7.1-2
Jan. 6 - Jan. 10	Random Walks on Undirected Graphs	MU: Chap. 7.3-4 Chiericetti, F., Dasgupta, A., Kumar, R., Lattanzi, S., Sarlos, T., On Sampling Nodes in a Network, Proceedings of the 25th International Conference on World Wide Web, 471--481, 2016.