Department of Computer Science and Technology

Course pages 2019–20

Introduction to Probability

Principal lecturers: Prof Mateja Jamnik, Dr Thomas Sauerwald
Taken by: Part IA CST 50%, Part IA CST 75%, Part IA NST

No. of lectures: 8
Prerequisite courses: XXXXXXXXX, XXXXXXXXXXXX
This course is a prerequisite for XXXXXX (Part II).


The aim of the course is to introduce the theory of computational complexity. The course will explain measures of the complexity of problems and of algorithms, based on time and space used on abstract models. Important complexity classes will be defined, and the notion of completeness established through a thorough study of NP-completeness. Applications to cryptographic protocols will be considered.


  • Introduction. Counting/Combinatorics (revision), Probability Space, Axioms, Union Bound.

  • Conditional probability. Conditional Probabilities and Independence, Bayes’Theorem, Partition Theorem

Part 2 - Discrete Random Variables

  • Random variables. Definition of a Random Variable, Probability Mass Function, Cumulative Distribution, Expectation.

  • Probability distributions. Definition and Properties of Expectation, Variance, different ways of computing them, Examples of important Distributions (Bernoulli, Binomial, Geometric, Poisson), Primer on Continuous Distributions including Normal and Exponential Distributions.

  • Multivariate distributions. Multiple Random Variables, Joint and Marginal Distributions, Independence of Random Variables, Covariance.

Part 3 - Moments and Limit Theorems

  • Title of lecture. Introduction: Law of Average, Useful inequalities (Markov and Chebyshef), Weak Law of Large Numbers (including Proof using Chebyshef’s inequality), Examples.

  • Title of lecture. Introduction to Moments of Random Variables, Central Limit Theorem (Proof using Moment Generating functions), Example.

Part 4 - Applications/Statistics

  • Title of lecture. Classical Parameter Estimation (Maximum-Likelihood-Estimation), bias, sample mean, sample variance), Examples (Collision-Sampling, Estimating Population Size).

  • Title of lecture. Online Algorithms (Secretary Problem, Odd’s Algorithm).


At the end of the course students should

  • be able to .....

  • be familiar with .....

  • understand .....

Recommended reading

* Author, A.N. (2004). Title of the book. Publisher.
Smith, X., Brown, Y. & Jones, Z. (2001). Title of the book. Publisher.