cs206 – Discrete Structures II

Instructor

Vladimir Pavlovic

Overview

CS206 is an introductory probability course. We will learn about combinatorics – different ways of counting events, discrete event probabilities, and, time-permitting, probabilities on continuous spaces.

Prerequisites: 198:205 and 640:152.

Topics

• Basic Ingredients (random experiment, sample space, events, probability measure).
• Conditional Probability, Bayes Theorem, Independence.
• Combinatorics and Counting.
• Recurrences, Generating Fns, and Applications.
• Random Variables.
• Bernoulli Trials.
• Expectation, Variance.
• Applications of Probability and Combinatorics.

Schedule

Topic	Description	Textbook
1	Introduction
2	Counting	Ross Ch.1 Rosen Ch.5
3	Piegeonhole principle	Ross Ch.1 Rosen Ch.6
4	Combinations and permutations Pascal's triangle	Ross Ch.1 Rosen Ch.6
5	Ordered sampling with replacement Catalan numbers	Ross Ch.1 Rosen Ch.5
6	Unordered sampling with replacement	Ross Ch.1 Rosen Ch.5
7	Sampling algorithms	Rosen Ch. 5
8	Probability	Ross, Ch.2
9	Probability axioms	Ross, Ch.2
10	Conditional probability	Ross, Ch. 3
11	Bayes rule	Ross, Ch. 3
12	Independence	Ross, Ch. 3
13	Random variables	Ross, Ch.4
14	Expecation and variance	Ross, Ch.4
15	Binomial and Bernoulli random variable	Ross, Ch.4
16	Poisson random variable	Ross, Ch.4
17	Negative binomial random variable	Ross, Ch.4
18	Continunous random variables	Ross, Ch.5
19	Sampling of random variables	Ross, Ch. 10
20	Gaussian random variable	Ross, Ch. 5 & 8
21	Joint random variables	Ross, Ch. 6
22	Transformation of random variables	Ross, Ch. 5 & 6

Textbooks

A First Course in Probability – Sheldon Ross, Prentice Hall, 9th ed., 2014.

Discrete Mathematics and its Applications – Kenneth A. Rosen
McGraw Hill, 7th ed., 2012 (Ch. 6-7)

Other

We use iClicker throughout the course.

You can also find an example of the course syllabus here.  Note that I will be distributing a new syllabus, which may differ from the one linked here, each term.