CS 237 - Probability in Computing

Fall, 2017

Instructor and Lecture

Times and Locations

Instructor:Wayne Snyder

      Email: waysnyder at gmail dot com


      Office: MCS 290

      Office Hours: W 3-6

      Tutoring Hours in Rich Hall: T 7:30-10:30pm

      Cell Phone: 617-966-(102+41) (text in an emergency; in general, email vastly preferred, but if you call, leave a message!)
;



Lecture: T, Th 11 - 12:15pm in CGS 511

Discussion/Labs:

      A2: M 1:25--2:15 (CAS 222)
      A3: M 12:20--1:10 (BRB 122)
      A4: M 3:35--4:25 (CAS 320)
      A5: M 4:40--5:30 (MCS B31)

TF: Kai Bernardini (kaidb@bu.edu)

 

Announcements:

After this first week, all announcements will be posted in Piazza and pinned to the top of the list.

Useful Links

 

 

Lecture
Date
Lecture & Lab Topics

Readings

PandS = "Schaum's Outline of Probability and Statistics"

Prob = "Schaum's Outline of Probability"

MCS = "Mathematics for Computer Science"

Practice Problems, Homeworks, and Tests
Labs
1 T 9/5

Administrative matters; Goals of the course; Motivating Examples: Why should you know probability and statistics? Probability and Statistics as the science of quantifying uncertainty. What is randomness? Probability and Computer Science.

 

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

Here is a nice exploration of the nature of randomness and our perceptions: HTML

   
2 Th 9/7 Basic definitions of probability theory: outcomes, sample spaces, probability functions, axioms for probability functions; examples of finite, countably infinite, and uncountable sample spaces and typical problems in each. Probability functions for finite, equiprobable spaces, and extention to uncountable case. Anomalies arising from infinite sample spaces.

Read PandS Ch. 1; this is very abbreviated, containing only the basic definitions;

Prob has a more extensive description of these concepts, and you may want to check that out, in sections 3.1 - 3.5.

Read through Ch. 1 & 2 in Prob if you need a review of the basic math background.

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

Practice problems from PandS (not to hand in): 1.1, 1.2 (a -- d), 1.3, 1.6 (a -- d).

HW 01: due Th 9/14 @ midnight

HW 01 Solution: PDF

 
         

Lab 01 (Jupyter Notebook -- right click and select Save Link As...)

Lab 01 Solution: ipynb

3 T 9/12 Set operations on events and axiomatic method for proving theorems about probability functions; non-equiprobable probability spaces.

Same readings as last time; also 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 Prob Chapter 3, but more rigorously, it is worth looking at for the application of the tree diagram technique.

Optional: Section 4.3 of Prob has a slightly different presentation of the tree diagram technique.

Prob p.94 has a nice explanation of trees resulting from independent trials (the simplest case).

 

The practice problems listed in the previous row apply to this lecture as well.

 

 

 
4 Th 9/14

Problem solving strategies; analysis using tree diagrams and the "Four Step Method"; the inverse method. Example: The Monty Hall Problem.

Conditional Probability; Independence.

This is still in PandS ch. 1; Prob Ch.4 has a more extensive treatment.

MCS 18.5 - 18.7 has the same material.

 

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

Tree diagram problems from Prob: 2.32, 2.33

Practice problems from PandS (not to hand in): 1.18, 1.11.

HW 02: HTML (due 9/21 @ midnight)

Solution: HTML

 

 
         

Lab 2 Reading: IPYNB (read carefully before the lab)

Lab 2 Problem Set: IPYNB (posted Monday before first lab)

Solution: IPYNB

5 T 9/19

Independence reviewed; Bayes' Rule.

Counting principles and combinatorics; inclusion-exclusion; counting as sampling and constructing outcomes.

Look at this summary of problem-solving strategies, most of which involve combinatorics: HTML; this is a good summary of what I will cover, although it does not explain all the formulae.

Bayes' Rule is covered well in Prob pp.90-91, including a nice explanation in terms of trees.

The form of Bayes' Rule in PandS p.8 and Prob p.90 is very general; we will discuss only the simple case P(B|A).

Prob p. 9 and MCS 14.9 discuss the inclusion-exclusion principle.

Prob discusses random sampling briefly in p.38; see also PandS on pp.153-4.

 

Practice problems from Prob (not to hand in): 4.22, 4.25 (Bayes), 2.2, 2.8,2.10

Practice problems from PandS (not to hand in): 2.4, 2.8, 2.12

 

 
6 Th 9/21 Review: selection with and without replacement; permutations; counting sets vs sequences; overcounting due to duplicates; multinomial coefficients; applications to finite probability problems.

Much of this should be review from CS 131!

Still in PandS ch. 1. (I told you it was very condensed!) You could also read Prob Ch. 2; MCS Sections 14.1 - 14.7 is a rather more advanced treatment of the same materal.

You should also read this link on Permutations with Repetitions;

 

Practice problems from Prob (not to hand in): 2.15,2.16, 2.17, 2.19, 2.20, 2.12

Practice problems from PandS (not to hand in): 1.20, 1.21, 1.23, 1.24, 1.25, 1.26, 1.69

HW 3: HTML

 
         

Here is an excellent short YT video on the basics of Poker: YT

Lab 3: HTML Poker Probabilities

7 T 9/26 Counting continued: the power set and counting subsets; combinations; verifying the poker probabilities; using combinations to count partitions; ordered partitions vs. unordered partitions.

Combinations are covered in the previous list of readings; Problem 1.36 on p.23 of PandS discusses poker probabilities; the Wiki article section on 5-card poker is very good; MCS 14.5 concerns powersets and counting subsets; here is a nice explanation about how to count partitions, with intuitive examples.

 

 

Practice problems from Prob (not to hand in): 2.24, 2.25, 2.26, 2.28, 2.29, 2.73

Practice problems from PandS (not to hand in): 1.27, 1.29, 1.30, 1.36

 
8 Th 9/28 Discrete Random Variables; Distributions; Probability Mass Function and Cumulative Distribution Functions. Read PandS pp.34-36 or Prob 5.1 - 5.3

Practice problems from Prob (not to hand in): 5.1 - 5.5, 5.8, 5.9

Practice problems from PandS (not to hand in): 2.12.2, 2.3

 
          Lab 4: HTML Implementing Random Variables; Displaying Distributions; Expected Payoff from Games
9 T 10/3 Expected value, Variance, and Standard Deviation of RVs; Standardized RVs; Functions of RVs

Read PandS pp.75 - 78 or Prob 5.4 - 5.5, 5.8

 

Practice problems from Prob (not to hand in): 5.15, 5.18, 5.19, 5.21, 5.23

Practice problems from PandS (not to hand in): 3.1, 3.2, 3.8

 

 
10 Th 10/5 Important Discrete Distributions: Uniform, Bernoulli, Binomial

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

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

Read Prob pp.177-180 or (brief) PandS p.108

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

Practice problems from PandS (not to hand in): 6.1,6.2,6.5,6.8

Lab 5 on Bloom Filters is a big one, so we will post this the previous week.
  T 10/10 Monday schedule: Labs will be held but no lecture!     Lab 5: Bloom Filters
11 Th 10/12

Discrete Distributions: Binomial concluded; Geometric; Memory-less property of Geometric.

  Practice problems from Schaum's (not to hand in): 6.38, 6.39.  
    Discrete Distributions: Poisson Distribution; Relationship between Binomial and Poisson.     Lab 6: Generating Random Variates for Discrete Distributions.
12 T 10/17 Joint Random Variables in discrete case; Independence of JRVs; Correlation of JRVs

Read Schaum's 5.6 - 5.7 (correct the bad typo on p.130, 4 lines from the bottom: μXμY should be σXσY)

Here is my spreadsheet from lecture: XLS

Practice problems from Prob (not to hand in): 5.25, 5.27, 5.31

Practice problems from PandS (not to hand in): 2.8, 2.9, 2.10

 

 

 

13 Th 10/19 Midterm (Date Tentative)      
          Lab 7: HTML (Fundamental Pitch detection using auto-correlation)
14 T 10/24 General (continuous) Random Variables; Uniform Distribution; Importance of CDF; Normal 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.  
15 Th 10/26 Normal Distribution, Exponential distribution; Memory-less property of Exponential Distribution.      
          Lab 8: Generating Random Variates for Continuous Distributions; Displaying Continuous Distributions.
16 T 10/31 Relationship between the Exponential and Poisson Distribution;      
17 Th 11/2 Central Limit Theorem Read 5.12, 6.5,

 

 
          Lab 9: HTML (Verifying the Central Limit Theorem)
18 T 11/7        
19 Th 11/9

Basic Statistics: Sampling theory, point estimation

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

Here is documentation on the scipy.norm statistics library: HTML
          Lab 10: HTML (Experiments with sampling and point estimates)
20 T 11/14 Confidence intervals      
21 Th 11/16 Hypothesis Testing      
          Lab 11: HTML (Reporting statistical analyses of experiments)
22 T 11/21 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

 
    Thanksgiving Recess      
23 T 11/28 Queueing Theory      
24 Th 11/30 Queueing Theory      
          Lab 12: HTML (Presentation of Final Project)
25 T 12/5 Random Walks      
26 Th 12/7 Random Walks and the Google Page Rank Algorithm      
          No Lab
27 T 12/12 Last Class: Conclusions and preparation for final exam      
           
  T 12/19 Final Exam: 12:30 - 2:30pm