CS 237 - Probability in Computing

Summer I, 2017

Instructor and Lecture

Times and Locations

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!)
;



Lecture: M - Th 11 - 1pm in MCS B19

Discussion/Lab:   T, Th 1 - 2pm in MCS B19 

TF: Femke Hermse (fhermse@bu.edu)

Grading

  • Here are the percentages I will use when assigning final grades:
  • 30% homeworks and labs (I will drop the lowest homework/lab 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
Date
Lecture & Lab Topics
Readings
Homeworks and Tests
Labs
1 T 5/23

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

Basic definitions of probability theory: outcomes, sample spaces, probability functions, axioms of probability; examples of finite, countably infinite, and uncountable sample spaces and typical problems in each. Definition of probability of event in equiprobable, finite case.

Here is a link to an article on traffic deaths after 9/11: 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

I covered approximately sections 3.1 - 3.5 in Schaum's, BUT without talking about using set operations (union, intersection, complement) on events (i.e., pp.63-65).

If you need a review of sets, read through chapter 1.

   
2 W 5/24 Probability spaces; Theorems on probability and set operations on events; non-equiprobable probability spaces; tree diagrams and the "Four Step Method". The Monty Hall Problem. The Birthday Problem.

Read Schaum's Chapter 3; read MCS sections 17.1 & 17.2 on the "Monty Hall Problem" and the "Four Step Method." Look at the link above to a video of the "Monty Hall Problem."

Optional: Section 17.5 from MCS covers the same material in Schaum's Chapter 3, but more rigorously, it is worth looking at for the application of the tree diagram technique.

Optional: Section 4.3 of Schaum's has a slightly different presentation of the tree diagram technique.

Practice problems from Schaum's (not to hand in): 3.2, 3.3, 3.5, 3.6, 3.7, 3.16, 3.18, 3.26.

HW 01: HTML

Solution: HTML

 
3 R 5/25 Conditional Probability

Read Schaum's Chapter 4 (whole thing)

MCS 18.5 - 18.7 has the same material, including Simpson's Paradox

Practice problems from Schaum's (not to hand in): 4.1, 4.4, 4.5, 4.6, 4.21, 4.22, 4.25, 4.26, 4.29, 4.36

HW 1: HTML

Lab and HW due Tuesday night 5/30 at midnight in the CS Homework Station.

Solution: HTML

Lab 1: HTML
  M 5/29 Holiday, no class  

 

 
4 T 5/30

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

Read Schaum's Chapter 2 and MCS Sections 15.1 - 15.7 (pp.609) -- This should be review from CS 131!

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

 

Practice problems from Schaum's (not to hand in): 2.4, 2.8, 2.12, 2.15, 2.16, 2.19, 2.23, 2.25, 2.29, 2.30, 2.33

HW 2: HTML

HW 2 Solution: HTML

Lab 2: HTML
5 W 5/31 Counting continued; multinomial coefficients, partitions Read this link on Permutations with Repetitions;

 

 
6 R 6/1 Random Variables; Expected value, Variance, and Standard Deviation; Distributions. Read Schaum's Chapter 5.1 - 5.5, 5.11

Practice problems from Schaum's (not to hand in): 5.1 - 5.5, 5.8, 5.9, 5.15, 5.18

HW 3: HTML

HW 3 Solution: HTML

Lab 3: HTML
7 F 6/2 Important Distributions: Uniform, Bernoulli, Binomial

Read Schaum's Chapter 6.2

For an illustration of the Binomial, take a look at this Quincunx animation: HTML

Practice problems from Schaum's (not to hand in): 6.2, 6.3, 6.5, 6.8, 6.12.

Here is a summary of some of the most useful discrete distributions: HTML (you do not need to know any that we did not study in lecture)

 
8 M 6/5 Important Distributions: Binomial, Geometric, & Poisson; Read Schaum's Chapter 6.7 and 6.8 (c) (p.195). Practice problems from Schaum's (not to hand in): 6.38, 6.39.  
9 T 6/6

Poisson continued; Relationship between Binomial and Poisson.

Discussion of homeworks 2 & 3; review for midterm.

 

 

 

No lab!
10 W 6/7 First Midterm Exam

Midterm 1 Solution: PDF

Here is last summer's exam: PDF  
12 R 6/8 Joint Random Variables in discrete case; Conditional JRV's; Independence of JRVs.

Read Schaum's 5.6 - 5.7.

Here is my spreadsheet from lecture: XLS

Practice problems from Schaum's (not to hand in): 6.25, 6.27, 6.29

HW 4: HTML

HW 4 Solution: HTML

Lab 4: HTML
13 M 6/12 No class (I was sick)

 

   
14 T 6/13 General (continuous) Random Variables; Uniform Distribution; Importance of CDF; Normal Distribution, Exponential distribution;

Read Schaum's 5.6, 5.7, 5.10, 6.3, 6.4

Lecture on Normal Distribution: PDF

6.5, 6.6, 6.9
There are practice problems at the end of chapter 5 of Schaum's, keyed to the relevant section: Look at practice problems for the sections I asked you to read.

Lab 5 (Generating Normal and Exponential Variates; Normal approximation to Binomial): HTML

Here is documentation on the scipy.norm statistics library: HTML

Starter code: Lab05.py

  W 6/14

Relationships between discrete and continuous distributions: Normal and Binomial; Exponential and Geometric; Exponential and Poisson

Review 5.6, 5.7    
  R 6/15 Limit Theorems; Central Limit Theorem Read 5.12, 6.5,

HW 5: HTML (due M 6/12)

HW 5 Solution: HTML

Look at relevant Schaum's problems.

Lab 6 (Pandas): HTML
  M 6/21 Missed Class

Read the Appendix of Schaum's on Statistics, your friendly neightborhood Statistics textbook, or here: PDF

   
  T 6/22

Basic Statistics: Sampling theory, point estimation, confidence intervals; Hypothesis Testing;

Schaum's Appendix A.5 - A.6

For practice look at Examples A.1 - A.6 in the text, then problem A.5

Here are additional problems from another Schaum's: PDF

No lab
  W 6/23 Joint Random Variables concluded: Scatterplots and linear regression; Schaum's Chapter 7;

HW 6: HTML

HW 6 Solution: HTML

For practice, look at Examples A.10 - A.13, then problem A.12.

Here are practice problems from another Schaum's: PDF

 
  R 6/24 CS Applications: Autocorrelation and Frequency Detection in Music Files; Queuing Theory     No lab
  M 6/26 Second Midterm

Solution: PDF

Here is the table of values for the CDF of the standardized normal distribution; be sure you know how to convert a given normal RV to the standard RV so you can look up the values.  
  T 6/27 Discussion of final homework   Final Homework: HTML  
  W 6/28 CS Applications: Probability and Complexity Theory; Discussion of Final Exam, and Evaluation      
  R 6/29 Final Exam      
  F 6/30 Final Homework Due at 5pm