• Course description:
  There is a body of tricks and techniques from elementary probability theory, whose mastery gives the user an amazing power in design and analysis of algorithms and in investigations of social and communication networks. We will analyze such tricks and techniques in an orderly and easily understandable way.

• Outline:
  Asymptotic approximations of factorials and binomial coefficients. Bonferroni inequalities. Finite probability spaces and random variables; the first and the second moment methods. Random graphs. Satisfiability problems. The Lovász Local Lemma. Concentration inequalities; martingales, Azuma's inequality, Talagrand's inequality. Correlation inequalities. Pseudorandomness, expanders, quasirandom structures. Circuit complexity. Derandomization.

• Prerequisites:
  Elementary calculus (finding extrema by differentiation, limits, l'Hôpital's rule, simple integrals).

• Instructor: Vašek Chvátal
  • Phone: (514) 848-2424   ext. 5767
    
  • Email:     c h v a t a l (at) c s e (dot) c o n c o r d i a (dot) c a
    
  • Office: Engineering, Computer Science, and Visual Arts Complex (EV) 3.107,
    1515 Ste-Catherine West
    
  • Office hours: by appointment

• Marker: None

• Classes: Fri 17:45 -- 20:15 in MB-S2.465, 1450 Guy.
  

• Grading scheme: There will be four homework assignments, a project, a midterm exam, and a final exam. The two exams will be closed-book exams (meaning that the students will be denied access to books, calculators, notes, etc.) and the final will be cumulative (meaning that it can draw on any material covered in the course). The overall numerical score will be calculated as 10% homework + 30% project + 20% midterm + 40% final. Letter grades will be derived from numerical scores roughly as follows:
  • score of at least 95 corresponds to A+
  • score of at least 85 and less than 95 corresponds to A
  • score of at least 75 and less than 85 corresponds to A-
  • score of at least 65 and less than 75 corresponds to B+
  • score of at least 55 and less than 65 corresponds to B
  • score of at least 50 and less than 55 corresponds to B-
  • score of at least 40 and less than 50 corresponds to C
  • score of less than 40 corresponds to F
  This guideline may be adjusted so as not to give students with very close numerical scores differing letter grades.

• Sources:
  • N. Alon and J.H. Spencer, The Probabilistic method (Third edition), Wiley, 2008.
  • M. Molloy and B. Reed, Graph colouring and the probabilistic method, Springer-Verlag, Berlin, 2002.
  • P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17--61.
  • R. Motwani and P. Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995.
  • E.M. Palmer, Graphical evolution, Wiley, 1985.
  • Collected Papers of Paul Erdős

  • Hypergraphs and Ramseyian theorems, Proc.Amer.Math.Soc. 27 (1971), 434-440.
  • J.L.W.V. Jensen, Sur les fonctions convexes et les inégalités entre les valeurs moyennes, Acta Mathematica 30 (1906), 175--193.
  • The Daykin-Erdős conjecture: original source and Richard Guy's report of it (see page 119).
  • H. Chernoff, A measure of asymptotic efficiency of tests of a hypothesis based on the sum of observations, Annals of Mathematical Statistics 23 (1952), 493--507.
  • P. Erdős and A. Rényi, On random graphs, I., Publ. Math. Debrecen 6 (1959), 290--297.
  • Leo Moser, The second moment method in combinatorial analysis, in: Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) pp. 283--284, Gordon and Breach, New York
  • Lovász Local Lemma: the original paper (pp. 616--617) and Alistair Sinclair's notes

  • The MacTutor History of Mathematics archive

• Class cancellations
• Code of Conduct (Academic)

• Solutions to primitive backgammon
• Solutions to the final exam
• Grades

To Vašek Chvátal's home page