Discrete Probability Theory for Computer Science
Overview
The course ends by continuing the introduction to discrete probability theory that was started in Computer Science 251. Results that are useful for the average-case analysis of algorithms, and the analysis of randomized algorithms, will be emphasized — and examples from computer science will be given.
This material will be covered in lectures on June 4 – 11 and in tutorials on June 8 – 11.
Supplemental Material
You should not need any reference material, for this, that is not provided on the course web site. However, the following book is an excellent reference for the material on discrete probability theory that is included in this course.
- D. Stirzaker, Probability and Random Variables:
A Beginner’s Guide
Cambridge University Press, 1999
It is freely available to students at the University of Calgary, as an ebook, through the university library. This sentence is a link to the ebook.
Lecture #10: Discrete Probability for Computer Science I (Thursday, June 4)
Why This is Included
Once again, you have to start somewhere! This lecture introduces sample spaces and probability distributions,, along with random variables and their expected values, which will be used to model and analyze experiments, for the rest of this course.
Almost everything in this lecture should be a review of material that was introduced in a prerequisite for this course. However, material concerning the expected value of a random variable, an example from computer science, and a small number of technical results will likely be material that students have not seen already.
Preparatory Viewing and Reading
- Reintroduction to Discrete Probability Theory [ Video: 25:12 ] [ PDF Slides ]
- Random Variables and Expectation [ Video: 15:32 ] [ PDF Slides ]
- Discrete Probability for Computer Science I — Key Concepts [ PDF ]
Supplemental Material
- What about Countably Infinite Sample Spaces? [ PDF ]
Lecture Presentation
Tutorial #9: Discrete Probability for Computer Science — Part One (Monday, June 8 and Tuesday, June 9)
This exercise concerns material from Lecture #10. Please read and try to solve the problems in this exercise before attending the tutorial where it is discussed.
Lecture #11: Discrete Probability for Computer Science II (Tuesday, June 9)
Why This is Included
There is often a numerical value, associated with an experiment, whose value we wish to study. This can generally be expressed as a “random variable”, and the expected value of this random variable will be of interest. However, we will often also be interested in the probability that this random variable's value is far away from its expected value — or is above (or below) a given threshold. The first part of this lecture includes notation and results that can often be used to compute or bound this kind of probability.
The final part of this lecture includes additional information about applications of discrete probability theory to the design and analysis of algorithms — including the introduction of various kinds of randomized algorithms that can fail (in limited ways) but are still, sometimes, useful.
Preparatory Viewing and Reading
- Tail Bounds [ Video: 26:31 ] [ PDF Slides ]
- Application: The Analysis of Algorithms [ Video:22:39 ] [ PDF Slides ]
- Discrete Probability for Computer Science II — Key Concepts [ PDF ]
Supplemental Material
- Proofs of Claims [ PDF ]
Lecture Presentation
Tutorial #10: Discrete Probability for Computer Science — Part Two (Wednesday, June 10 and Thursday, June 11)
This exercise concerns material from Lecture #11. Please read and try to solve the problems in this exercise before attending the tutorial where it is discussed.
Lecture #12: Discrete Probability for Computer Science III (Thursday, June 11)
Why This is Included
“Classical” probability distributions arise when probability theory is being used to solve problems, over and over again. However, the language used in an application area might not be the language used in a textbook on probability and statistics, so these distributions might appear in a somewhat “disguised” form. If you are already familiar with these classical probability distributions then you will, ideally, recognize them — so that you can look for and make use of helpful material about these classical distributions in the “probability theory” literature.The beginning of the lecture presentation concerns material introduced in Lecture 11 — but classical probability distributions are also (briefly) considered at the end.
Note: For the purposes of this course, this is “for interest only:” students will not be examined on this material in CPSC 351.
Preparatory Viewing and Reading
- Classical Probability Distributions [ Video: 14:27 ] [ PDF Slides ]
- Discrete Probability for Computer Science III — Key Concepts [ PDF ]
