Lecture: Tue, 9:00, S1, Tereza Klimošová and Matěj Konečný
Tutorials: Tue, 15:40, S8, Tomáš Hons and Giuseppe Pino, webpage for tutorials.

List of topics covered by lectures is at the bottom of this webpage.

Office hours: By individual arrangement by email: tereza@kam and matej@kam, where 'kam' stands for kam.mff.cuni.cz.

Exams: Exam times will be scheduled by individual arrangement. Let both of us know by email: tereza@kam and matej@kam, where 'kam' stands for kam.mff.cuni.cz, when you are available to take an exam.

Annotation: Probabilistic techniques are a major tool of discrete mathematics, they are also frequently used in design and analysis of algorithms and other areas of computer science. The lecture introduces basic notions, methods, and estimates and illustrates them on examples from computer science and discrete mathematics.

• Basic notions and methods: events, expected value and its linearity, conditional probability, Bayes' rule.
• Basic inequalities and estimates: Markov's and Chebyshev's inequality, Chernoff-type estimates.
• Probabilistic method: basic method and alteration method, Lovász local lemma.
• Advanced techniques: balls and bins model, basic estimates and applications, Markov chains, stationary distribution, basic continuous distributions as limits of discrete ones, properties and applications.

• [AS] N. Alon, J. Spencer: The Probabilistic Method, J. Wiley and Sons 1993, 2008, 2015, pdf.
• [MU] M. Mitzenmacher, E. Upfal: Probability and Computing, Cambridge University Press, 2005, pdf.
• [MR] M. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995.
• [O'D] R. O'Donell: Probability and Computing, lecture notes .
• [[MV] J. Matoušek, J. Vondrák: The Probabilistic Method, ITI Series (preprints Institute of Computer Science, MFF UK), 2002-087; pdf .