CS 237 - Probability in Computing

Spring, 2021

Instructor and Lecture

Times and Locations


Instructor:Wayne Snyder

     Email: waysnyder at gmail dot com


      CS 237 Office Hours: After lecture and W 10-11, 5-6+pm (I'll stay as long as people have questions)

      Lecture Zoom:: https://bostonu.zoom.us/j/95795215342?pwd=aVZ0Y01pQWVRK2tiRkJZRU0rV0Z6QT09
      Snyder Office Hours Zoom:: ZOOM

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



Lecture: T Th 3:30 - 5:00pm

Teaching Fellow:

      Richard Andreas (ra7296 at bu dot edu)
      Office Hours: M 10-11, Th 12-1

Useful Links

Lecture
Date
Lecture Topics

Readings and Resources

Practice Problems and Tests
Homeworks/Labs
0 Th 1/29

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?

Lecture Slides: PDF

Required Reading: Textbook §1.1

Optional: Here is a nice exploration of the nature of randomness and our perceptions: 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): YT

For a wonderful and informative video by an expert mathematician about randomness and cards, see the YouTube video here.

 

Python Resources CS 237: HTML

Summary of Python (with examples) for CS 237: IPYNB,   ZIP

HW 01: IPYNB,   ZIP

HW 01 Solution: IPYNB,   ZIP

1 T 2/2 Basic definitions of probability theory: outcomes, sample spaces, probability functions, axioms for probability functions.

Lecture 01: PDF

Required Reading: Textbook §1.3.1, 1.3.2

Review §1.2 as needed for math background.

Optional (on infinite sets and countability): Math for Computer Science, § 7.1, p.192.

Proof that reals are not countable: YT

Textbook practice problems (Optional but recommended): P1 - P5

2 Th 2/4 Set operations on events and axiomatic method for proving theorems about probability functions;Axioms continued; Examples of finite, countably infinite, and uncountable sample spaces and typical problems in each. Probability functions for finite, equiprobable spaces, and extension to uncountable case. Anomalies arising from infinite sample spaces.

Lecture 02: PDF

Required Reading: Textbook § 1.3.3 - 1.3.4

YouTube Video about axiomatic proofs: YT

Textbook practice problems (Optional but recommended): P1 - P5

Markdown Tutorial: IPYNB

HW 02: IPYNB, ZIP

HW 02 Solution: PDF

3 T 2/9

Non-Equiprobable sample spaces; Problem solving strategies; analysis using tree diagrams and the "Four Step Method"; the Inverse Method. If time: The Monty Hall Problem.

Lecture 03: PDF

Required Reading: Math for Computer Science, § 16.1 & § 16.2 on the "Monty Hall Problem" and the "Four Step Method.

Optional: Look at the link above for a video of the "Monty Hall Problem" from the movie 21 (featuring Kevin Spacey in better times); the scene shown was filmed in the CAS building.

4 Th 2/11

Conditional Probability and Introduction to Independence

Lecture Slides: PDF

Required: § 1.4.0 -- 1.4.1

Optional: Wikipedia on the Base Rate Fallacy: HTML

Textbook practice problems (Optional but recommended): P1 - P8

 

HW 03: IPYNB, ZIP

HW 03 Solution: PDF

T 2/16

No Class: Monday Schedule

5 Th 2/18

Independence, Conditional Independence, and Bayes Rule

Lecture Slides: PDF

Required: textbook § 1.4.2 - 1.4.4

 

HW 04: IPYNB, ZIP

HW 04 Solution: PDF

6 T 2/23

Counting principles and combinatorics; counting as sampling and constructing outcomes. Selection with and without replacement; permutations; counting sets vs sequences; the Unordering Principle; overcounting due to duplicates, multinomial coefficients.

Lecture Slides: PDF

Required: Read Chapter 2 up through 2.1.2

Also, review the Inclusion/Exclusion Principle in section 1.3.3.

 
7 Th 2/25 Combinations and "N choose K"; Applications to probability problems. Poker hands will be used to illustrate these counting principles.

Lecture Slides: PDF

Required: Read 2.1.3 up to Bernoulli Trials up through 2.1.2

Optional: Secrets of Pascal's Triangle

Optional: This Wiki article section on 5-card poker is very good;

HW 05: IPYNB, ZIP

HW 05 Solution: PDF

8 T 3/2 Poker Probability continued; Using combinations to count partitions; ordered partitions vs. unordered partitions; overcounting due to duplicates among subsets.

Lecture Slides: PDF

No new reading

MCS § 14.5 concerns powersets and counting subsets; ;

Here is a nice explanation about how to count partitions, with intuitive examples.

9 Th 3/4

Combinatorics and Finite Probability concluded; Choosing Multisets without Replacement


Lecture Slides: PDF

HW 06: IPYNB,   ZIP

HW 06 Solution: PDF

10 T 3/9

Discrete Random Variables; Functions and Expressions of RVs;

Functions and expressions of random variables; (if time) independent and conditional random variables


Lecture Slides: PDF

Required: 3.1.1 - 3.1.4. (you do not need to read about the hypergeometric, or the Poisson (yet))

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

Textbook practice problems (optional but recommended): Ch. 3.1, Problems 1 -- 4

11 Th 3/11

Finish independent and conditional RVs; Discrete Distributions: Bernoulli, Binomial, Geometric, and Pascal (Negative Binomial); Cumulative Distribution Functions

Lecture Slides: PDF

Required: 3.1.5

Distributions Notebook: IPYNB,   ZIP

HW 07: IPYNB,   ZIP

Solution: PDF

12 T 3/16 Finish Standard Discrete Distributions, memory-less property of Geometric; Introduction to Games and Expectation of RVs
Lecture Slides: PDF

Required: 3.2.1-3.2.2

The Wiki article on the memoryless property is good, especially the examples on Waiting Times: HTML

Textbook practice problems (Optional but recommended): Ch. 3.2, Problems 1 - 3

Th 3/18

No Lecture: BU Wellness Day

F 3/19

No Lab; Midterm Review Video and Sample Tests

Directory of past midterm solutions: DIR

Sample problems and solutions on combinatorics: PDF

Sample problems and solutions on basic probability: PDF

Sample problems and solutions on conditional probability and independence: PDF

T 3/23

Midterm

Midterm Solution: PDF

13 Th 3/25

Expectation of RVs concluded; properties of expectation; expectation of special distributions

Lecture Slides: PDF

Required: 3.2.2 (on expectation)

Reading for the lab: OOP in Python

HW 08: IPYNB,   ZIP

HW 08 Solution: PDF

14 T 3/30

Expectation, Variance, Limit Theorems

Lecture Slides: PDF

Required: 3.2.4

15 Th 4/1

Continuous Random Variables; the Normal Distribution  

Lecture Slides: PDF

Brief video on integration for CS 237: YT

Required (continuous distributions): 4.1.0 - 4.2.1, and 4.2.3

Textbook practice problems (Optional but recommended): Problems 1, 3, 4

HW 09: IPYNB ZIP

HW 09 Solution: PDF

16 T 4/6

Normal Distribution and the Normal approximation to the Binomial; the Continuity Correction

Lecture Slides: PDF

Required (special continuous distributions): 4.2.3

17 Th 4/8 Central Limit Theorem and its Applications: Sampling

Lecture Slides: PDF

Jupyter notebook on CLT IPYNB  ZIP

HW 10: IPYNB, ZIP

Solution: PDF

18 T 4/13 Statistics as Applications of the CLT: Confidence Intervals

Lecture Slides: PDF

Nice intro talk on : statistics in Python

 
19 Th 4/15

Hypothesis Testing

Lecture Slides: PDF

 

HW 11: IPYNB, ZIP

Solution: PDF

20 T 4/20 Poisson Process: Counting processes, Poisson (Discrete) Distribution, relationship between Poisson and Exponential. Applications to Waiting Time problems and analysis of queues.

Lecture Slides: PDF

Optional: A fun blog post about waiting times: HTML

Optional: Here is the New Yorker article about earthquakes in the Pacific Northwest. Not-so-fun facts: (1) "the Pacific Northwest has experienced forty-one subduction-zone earthquakes in the past ten thousand years. If you divide ten thousand by forty-one, you get two hundred and forty-three," which is the mean; and (2) the last subduction-zone earthquake was in 1700, or 320 years ago.

21 Th 4/22 Joint Random Variables; Independence, Covariance, and Correlation

Lecture Slides: PDF

Chapter 5.1.1, 5.1.3

For continuous joint random variables, this is a reasonable introduction to the main points: HTML

HW 12: IPYNB, ZIP

Solution: PDF

22 T 4/27 Linear Regression: Least Squares Solutions, Linear Models

Lecture: PDF

Notebook with Examples: IPYNB

Chapter 8.5

23 Th 4/29 Multiple Regression, Machine Learning

Lecture Slides: PDF

For Multiple Regression, I will follow fairly closely the treatment in sections 5.1 - 5.4 in this link.

  T 5/4 Final Exam from 3 - 5pm

Final Exam (Notebook): IPYNB

Final Exam (Zipped Notebook): ZIP

Final Exam (Word): DOCX

Final Exam (PDF): PDF

Distributions Cheatsheet (will be provided on exam): PDF

Directory of Past Exams: DIR

Practice Final Exam: IPYNB

Practice Final Exam:DOCX

Practice Final Exam:PDF

Practice Final Exam Solution:PDF