The Probabilistic Method is a powerful tool in tackling many problems in discrete mathematics. It belongs to those areas of mathematics which have experienced a most impressive growth in the past few decades. Roughly speaking, its basic idea can be described as follows. In order to prove existence of a combinatorial structure with certain properties, we construct an appropriate probability space, and show that a randomly chosen element of this space has the desired property, with positive probability. This course provides a gentle introduction to the Probabilistic Method, with emphasis on methodology. We will try to illustrate the main ideas by showing the application of probabilistic reasoning to various combinatorial problems.
- The Probabilistic Method, Third Edition, 2008, by N. Alon and J.H. Spencer
Class time and Location:
Saturday and Monday 10:00-12:00 AM (Fall 2018), Room 204/1.
General mathematical sophistication; and a solid understanding of Algorithms, Linear Algebra, and Probability Theory, at the advanced undergraduate or beginning graduate level, or equivalent.
- Homework – 10%
- Midterm – 40%
- Endterm – 50%
Midterm Examination 1: Monday, 95/02/06, 10:00-12:00 AM
Midterm Examination 2: Saturday, 95/03/01, 10:00-12:00 AM
Final Examination: Monday, 95/03/10, 08:00-12:00 AM
I’ll be having office hours for this course on Saturday and Monday 08:30–10:00 AM. If this isn’t convenient, email me at email@example.com or talk to me after class.
Stu. Num. Midterm 1 Midterm 2 Homework Final
94422052 26.3/30 26/30 3.9/5 9.9/12
93422001 3.8/50 18.5/30 2/5 4/12
94420000 19.2/30 17.5/30 2/5 6.9/12
M. M. 26.7/30 28.5/30 5/5 9/12