Discrete Probability 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 om lectures on November 5 – December 3 and in tutorials on November 18 – December 3.
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 5)
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.
Preparatory Reading
Lecture Presentation
Finishing Up
Additional Information That Might Be Useful
There seem to be lots of online tutorials available that introduce discrete probability theory. Many of them — unfortunately, like this one — only seem to refer to uniform probability distributions when introducing probability distributions. This tutorial might still be helpful, in spite of that.
Lecture #19: Conditional Probability and Independence (Thursday, November 7)
Why This is Included
We are often interested in multiple events, and the relationships between them. It is also sometimes possible to compute the probability of a complicated event by considering other events and using these to introduce multiple simpler cases that can be considered instead. This lecture introduces notation and some results that are needed for this.
Once again, quite a bit of the material in this lecture should be material that most students in the class have seen before — but new material may appear, near the end.
Preparatory Reading
- Conditional Probability and Independence: [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #15: Introduction to Discrete Probability Theory for Computer Science (Monday, November 18 and Tuesday, November 19)
Lecture #20: Random Variables and Expectation (Tuesday, November 19)
Why This is Included
There is often a numerical value, associated with an experiment, whose value we wish to know. Indeed, computing (or estimating, or bounding) this value may be the main reason to consider the experiment at all. This lecture introduces notation and some results that are needed for this.
While many students will have seen quite a bit of this material already, some have reported, in past terms, that they have not remembered seeing any of it at all. In any case it is likely, once again, that there will be some new material near the end.
Preparatory Reading
Lecture Presentation
Finishing Up
Tutorial #16: Random Variables and Expectation (Wednesday, November 20 and Thursday, November 21)
Lecture #21: Tail Bounds
(Thursday, November 21)
Why This is Included
As noted above, there is often a numerical value, associated with an experiment, whose value we wish to know about. This can be modelled using a random variable whose expected value can be computed or bounded.
We might 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. This lecture includes notation and results that can often be used to compute or bound this kind of probability.
Preparatory Reading
- Tail Bounds: [ PDF ] [ Video ]
- Supplement: Proofs of Claims [ PDF ]
- Supplement: What about Countably Infinite Sample Spaces? [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #17: Tail Bounds (Monday, November 25 and Tuesday, November 26)
Lecture #22: Application — The Analysis of Algorithms (Tuesday, November 26)
Why This is Included
While the worst-case analysis of an algorithm is often important, this might not describe how the algorithm behaves “most of the time“ — and this might be what someone is most interested in, when they want to make a choice between algorithms.
It is sometimes possible to produce algorithms that are simpler or (at least slightly) faster, than would otherwise be the case, if these algorithms are allowed to make random choices.
This lecture describes how probability theory can be applied to perform an average-case analysis of an algorithm, to understand how it behaves in practice. It also introduces several kinds of randomized algorithms that have been studied and used.
Preparatory Reading
Lecture Presentation
Finishing Up
Tutorial #18: Application — The Analysis of Algorithms (Wednesday, November 27 and Thursday, November 28
Lecture #23: Classical Probability Distributions (Thursday, November 28)
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.
Note: For the purposes of this course, this is “for interest only:” students will not be examined on this material in CPSC 351.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #24: Randomly Constructed Binary Search Trees (Tuesday, December 3)
Why This is Included
Binary search trees are often used to implement “dictionaries” because their performance, in practice, is so good, even though operations can use time that is linear in the size of the dictionary being represented, in the worst case.
The analysis in this lecture provides additional evidence that these data structures will work well, when assumptions about their creation (and distribution) hold. It also provides additional evidence that the material about discrete probability, introduced in this course, is useful for solving problems in computer science.
Note: For the purposes of this course, this is “for interest only:” students will not be examined on this material in CPSC 351.
Preparatory Reading
- Randomly Constructed Binary Search Trees [ PDF ]
