CS 203: Mathematics for Computer Science III

Announcements

Course Notes

Topic Link
Introduction to probability, basic framework Introduction
Conditional probability, Bayes theorem, Monty Hall problem Conditional probability
Program for Bayes Theorem Bayes Theorem
Random variables, expectation, distributions Random variable
Markov inequality, Law of large numbers, Chernoff bound Concentration inequalities
Independence (pairwise and mutual), applications Independence
Markov chains, stationary distribution and web-page search Markov

Course description

Probability theory is the study of probability and random process. Probability theory aims to define a rigorous mathematical framework to study these questions. The applications cover almost all aspects of computer science. Most notably, in recent times, probability theory has attracted lot more interest because of its use in machine learning (through statistics and even directly) and quantum computing (through postulates of quantum mechanics).

We will start by covering the mathematical framework of sample space and events. We will go through examples (probably covered in high school) based on this framework. Next, random variables and probability distributions will be covered. The final part of basics would be conditional probability.

We will cover the idea of independence and concentration inequalities in the mid part of this course. They will be explained with examples from the world of computer science. The final part, if time permits, will be statistics and probabilistic methods.

Administrative details

References