CS 237 - Probability in Computing

Summer I, 2016

Instructor and Lecture

Teaching Fellow and Lab Sections

Instructor:Wayne Snyder
      Email: waysnyder at gmail dot com
      Office: MCS 290
      Office Hours: TBA

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

Teaching Fellow: Zhe

Discussion Section:


  • Here are the percentages I will use when assigning final grades:
  • 30% homeworks (I will drop the lowest homework score)
  • 20% for each of two midterms every two weeks (second will cover only material since first midterm)
  • 30% for cumulative final exam (last day of class)

Useful Links

Lecture & Lab Topics
Readings, from Bertsekas unless otherwise noted
Homeworks and Tests
1 M 5/23

Administrative matters; Goals of the course; Motivating Examples: Why should a computer scientist know probability and statistics?

Introduction to Classical Probability: Coin flips and random choices. Set theory and probability.

Here is chapter one of The Drunkard's Walk (the whole thing is worth reading, but I will talk about the flight instructors example on pages 7 and 8): PDF

Here is a link to an article on traffic deaths after 9/11: HTML

Here is the New Yorker article on earthquakes in the Pacific Northwest: HTML

Here is the wiki page explaining the "Base Rate Falacy" (look at Example 1, on breathalyzer tests): 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, in a later lecture): HTML

Sections 1.1 - 1.2 (PDF)

2 T 5/24 Classical Probability Sections 1.1 - 1.2 (PDF)


Solution: HTML

3 W 5/25 Classical Probability



  R 5/26 Conditional Probability  


Solution: HTML

4 T 5/31

Total Probability Theorem and Bayes' Theorem; Independence

Section 1.3 & 1.4


Solution: HTML

5 W6/1

Counting principles and combinatorics; permutations and combinations; accounting for duplicates; permutations; applications to probability problems.

Section 1.6

Also, look at this summary of problem-solving strategies, most of which involve combinatorics: HTML



6 R 6/2 Counting continued; multinomial coefficients Read this link on Permutations with Repetitions;    
7 F 6/3 Random Variables; Binomial Distribution

Section 2.1 & 2.2


Solution: HTML

Here is a summary of some of the most useful discrete distributions: HTML (so far we have done only Bernoulli, Binomial, and Geometrical)

Here are some useful Python functions: Distributions.py

8 M 6/6 Important Distributions: Binomial, Geometric, Poisson


Here are the first five chapters from Schaum's, with lots of practice problems (with solutions): 1, 2, 3, 4, 5  
9 T 6/7 First Midterm Exam Midterm Solution: PDF


Solution: HTML

10 W 6/8 Discrete Distributions continued: Expected values, variance, standard deviation; Joint Random Variables Here is a spreadsheet to work with joint random variables: JointDistributions.xlsx    
11 R 6/9 JRVs: Conditional, Independence  


Solutions: HTML

12 M 6/13 Discrete JRVs concluded: Relationship of Binomial and Poisson; Covariance and correlation, expected value and variance of sums of RVs; Sampling as repeated sum of RV.

Cov & cor are in section 4.2;

Expected value and variance of sum of RVs is at end of chapter 2, or you can also see a brief summary here: HTML

Here is my spreadsheet from lecture: XLS


Solution: HTML

13 T 6/14 General (continuous) Random Variables; probabilities as areas under a curve; PDFs and CDFs.; Normal Distribution, Exponential Distribution

Chapter 3

Lecture on Normal Distribution: PDF

  W 6/15 Exponential distribution; relationship of Exponential and Geometric; relationship of Exponential and Poisson; Normal approximation to Binomial; Chapter 3 Here is a collection of all kinds of functions related to distributions, which I was using in class today: Distributions.py  
  R 6/16 Joint Continuous RVs Chapter 3    
  M 6/20 Limit Theorems; Central Limit Theorem Chapter 4


Solution: HTML

  T 6/21 Introduction to Statistics: Sampling theory, point estimates, confidence intervals, hypothesis testing

Chapter 9.1

For a more basic introduction, consult your friendly neighborhood statistics textbook on the topics listed, or here: PDF

  W 6/22 Small sample estimation: the t-distribution; Chapter 9.1 & 9.2    
  R 6/23 Second midterm   HW 09: HTML (due next Wednesday)  
  M 6/27 Linear Regression; Chi-Squared test; Distribution Fitting

Chapter 9 has a good description of regression and its motivations, and on the Chi-Squared Test (p.505); there are many other treatments of this material, e.g., HTML

  T 6/28 Distribution Fitting: Error margins, regression and normal plots Here is a research paper on normal plots: PDF; the "Background and Motivation" section describes the basic idea.    
  W 6/29 Review of HW 09; Course evaluations and conclusions.      
  R 6/30 Final Exam