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

TopicDescriptionTextbook
1Introduction
2CountingRoss Ch.1
Rosen Ch.5
3Piegeonhole principleRoss Ch.1
Rosen Ch.6
4Combinations and permutations
Pascal's triangle
Ross Ch.1
Rosen Ch.6
5Ordered sampling with replacement
Catalan numbers
Ross Ch.1
Rosen Ch.5
6Unordered sampling with replacementRoss Ch.1
Rosen Ch.5
7Sampling algorithmsRosen Ch. 5
8ProbabilityRoss, Ch.2
9Probability axiomsRoss, Ch.2
10Conditional probabilityRoss, Ch. 3
11Bayes ruleRoss, Ch. 3
12IndependenceRoss, Ch. 3
13Random variablesRoss, Ch.4
14Expecation and varianceRoss, Ch.4
15Binomial and Bernoulli random variableRoss, Ch.4
16Poisson random variableRoss, Ch.4
17Negative binomial random variableRoss, Ch.4
18Continunous random variablesRoss, Ch.5
19Sampling of random variablesRoss, Ch. 10
20Gaussian random variableRoss, Ch. 5 & 8
21Joint random variablesRoss, Ch. 6
22Transformation of random variablesRoss, 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.