Sets, The concept of a discrete sample space in probability theory. The definition of an event. The definition of a probability distribution. Random variables, expectation and variance.
Discrete distributions: Bernoulli trials, Geometric, Binomial and Hypergeometric and Negative Binomial distributions, Poisson distribution. Continuous distributions: normal and other continuous distributions Exercises based on the analysis of applications to computer science.
Linearity of expectation. Higher moments of a random variable, moment generating function. Computing the moments of geometric, binomial, normal and Poisson distributions.
Conditional Probability, Conditional expectation of a random variable with respect to an event. Bayes' Theorem and examples of applications in computer science.
The concept of k-wise and mutual independence of random variables. Applications of independence and k-wise independence in computer science.
Tail bounds: Markov inequality, Chebyshev's Inequality, Chernoff bound, and Examples of applications to the analysis of randomized algorithms.
Introduction to the probabilistic method. Applications to random graphs and number theory. Lovasz Local Lemma and applications.
If time permits, one of the following topics can be covered: Information theory/ Markov chains/ Randomized algorithms/ Streaming.