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 November 4 – December 2 and in tutorials on November 17 – December 2.
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 #18: Probability Distributions (Tuesday, November 4)
Why This is Included
Once again, you have to start somewhere! This lecture introduces sample spaces and probability distributions, 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 — but an example from computer science, and a small number of technical results, will likely be material that students have not seen already.
