CS 237 - Probability in Computing

Fall , 2015

Instructor and Lecture

Teaching Fellow and Lab Sections

Instructor:Wayne Snyder
      Email: waysnyder at gmail dot com
      Office: MCS 147
      Office Hours: T 1:30-2:30 W 2:30 - 4:30 R 12:30 -2:00

      Cell Phone: 617-966-(10^2+41) (email vastly preferred, but if you call, leave a message!)

Teaching Fellow: Hannah Flynn
      Email: hmflynn at bu dot edu

     Office: PSY 221
      Office Hours: T 2-3 in CS Ugrad Lab (above Radio Shack)

Discussion Sections (all on Mondays)
1-2pm in MCS B21

     A3: 2-3pm in PSY B49
      A4: 3-4pm in MCS B25

Announcements and Assignments:

  • Our first quiz will occur on Tuesday 9/29, at the end of class; there will be no computation on the quiz: I am going to give you a list of problems and you need to tell me which technique or formula would apply (e.g., it is a permutation with replacement, or it is a permutation with repetitions).
  • Here is a brief summary of the problem solving techniques we have studied so far: HTML


Useful Links

Lecture & Lab Topics
Readings, from DeGroot unless otherwise noted
Homeworks and Tests
1 R 9/3 Administrative matters; Goals of the course; Motivating Examples: Why should a computer scientist know probability and statistics?

Recommended: Chapter One from "The Drunkard's Walk": PDF

Here is a link to an article on traffic deaths after 9/11, with slightly different numbers than I presented: HTML

Here is the wiki page explaining the "Base Rate Falacy" (the breathalyzer example at the end of class): HTML

Just for Fun: Here is a short YT video with various clips from movies which involve probability (we will return to the Monty Hall Problem, the first clip, next week): HTML

2 T 9/8 Classical Probability: Basic definitions; Set theory (e.g., Venn Diagrams) as a model for Sample Spaces and Events; Geometric Probability (uncountable sample spaces). Sections 1.1 - 1.4    
3 R 9/10 Axioms and theorems of probability; Geometric Probability (uncountable sample spaces);

Section 1.5 -- We will cover this in detail; pay particular attention to last two pages, on uncountable sample spaces!

Section 1.6 -- We basically covered this in class today, but review it!


Solution: HTML

  M 9/14 Lab 01: Generating random numbers and running simulations    

Lab 01: HTML

Solution: TXT

4 T 9/15

The general Inclusion/Exclusion Principle; Combinatorics and counting finite sets; Multiplication principle and tree diagrams; The Monty Hall Problem (application of the Multiplication Principle); Choosing with and without replacement; Permutations.

Read this short article on the Inclusion-Exclusion Principle: HTML and then read page 48 (skipping the proof if you like....) in the textbook.

Sections 1.7 (main reading)

Also Google "probability tree diagram" and read the first link (easy) and then read sections 14.1 and 14.2 of the following analysis of the "Monty Hall Problem": PDF

5 R 9/17

Counting principles continued; permutations and combinations; accounting for duplicates; applications to classical probability.

Section 1.8


Solution: HTML

  M 9/21 Lab 02: Computing with permutations and combinations; simulation continued. Read about Pascal's Triangle and its relationship to C(N,K) here.  

Lab 02: HTML

Solution: TXT

6 T 9/22 Counting concluded: combinations and subsets; accounting for repetitions; multinomial coefficients;

Section 1.8,

Read this link on Permutations with Repetitions;

Section 1.9

7 R 9/24 Discrete non-equiprobably sample spaces; Histograms vs distributions; Conditional Probability

Read about Histograms here:

Section 2.1



Solution: HTML

  M 9/28 Lab 03: Drawing probabilities in Python: PMFs and CDFs    

Lab 03: HTML

Solution: TXT

8 T 9/29 Conditional Probability; Independence Section 2.2 Quiz 01 at end of class;  
9 R 10/1 Bayes Theorem, Discrete Random Variables; Distributions, PMFs and CDFs

Read about Bayes Theorem here: HTML

Just read the first two screenfuls or so, with the background, statement of the theorem and the example about Addison.

Read chapter 3.1 up to page 98 on Discrete Random Variables. This is just a way of formalizing what we have already been doing!


Solution: HTML

  M 10/5 Lab 04    

Lab 04: HTML

Solution: TXT

10 T 10/6 Properties of random variables: Expected value/mean, mode, variance, standard deviation, skew

Our textbook spreads out the various characteristics of random variables, and I would rather you read Chapter Five from the Schaum's, which I provide since not all of you will have bought it: PDF

This reading uses f(x) instead of p(x) for the PMF, but otherwise it is fairly consistent with what we have been doing.

11 R 10/8 Bernoulli Trials, Binomial Distribution  


Solution: HTML

  T 10/13 Monday Schedule; Lab 05      
12 R 10/15 Poisson Distribution  


Solution: HTML

  M 10/19 Lab 06    

Lab 05: HTML

Solution: TXT

13 T 10/20 Geometric Distribution;      
14 R 10/22 Joint random variables & joint distributions  


Solution: HTML

  M 10/26 Lab 07    

Lab 06: HTML

Solution: TXT

15 T 10/27 Covariance, Correlation  

HW07 (short): HTML

Solution: HTML

  W 10/28 Midterm Review Session at 7pm, location TBA  


  R 10/29 Midterm (tentative)  


  M 11/2 Lab 08    

Lab 07: HTML

Solution: TXT

16 T 11/3 Regression and curve fitting      
17 R 11/5 Continuous random variables; the normal distribution;  


Solution: HTML

  M 11/9 Lab 09: Approximating the binomial with the normal distribution; Continuity correction for normal approximation to binomial    

Lab 08: HTML

Solution: TXT

18 T 11/10 Central Limit Theorem; Law of Large Numbers      
19 R 11/12 Continuous Distributions: Poisson  


Solution: HTML

  M 11/16 Lab 10: Demonstrating the CLT    

Lab 09: HTML

Solution: TXT

20 T 11/17 Continuous Distributions: Exponential      
21 R 11/19 Intro to Statistical Thinking: Sampling and sample statistics  


Solution: HTML

  M 11/23 Lab 11:    

Lab 10: HTML

Solution: TXT

22 T 11/24 Statistics:      
23 R 11/26 Statistics  


Solution: HTML

  M 11/30 Lab 12    

Lab 11: HTML

Solution: TXT

24 T 12/1 Statistics      
25 R 12/3 Markov Processes  


Solution: HTML

  M 12/7 Lab 13    

Lab 12: HTML

Solution: TXT

26 T 12/8 Markov Processes      
27 R 12/10    


Solution: HTML

  R 12/17 Final Exam 12:30 - 2:30pm