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 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:: https://bostonu.zoom.us/j/5616300723

      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: TBA

Useful Links

Lecture
Date
Lecture Topics

Readings and Resources

Practice Problems and Tests
Homeworks/Labs
0

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

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

 

Python Resources CS 237: HTML

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

1 What is randomness? Basic definitions of probability theory: outcomes, sample spaces, probability functions, axioms for probability functions.

Lecture 01: PDF

Required Reading: Textbook §1.1, §1.3

Review §1.2 as needed for math background.

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

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

HW 01 A : IPYNB

HW 01 B Solution: IPYNB

2 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

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

Proof that reals are not countable: YT

YouTube Video about axiomatic proofs: YT

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

3

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.

No slides, I used the board!

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

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

HW 02: IPYNB

Numpy Tutorial: IPYNB

4

Conditional Probability and Independence Bayes Rule

Lecture Slides: PDF

Required: § 1.4.1 -- 1.4.4

Optional: Wikipedia on the Base Rate Fallacy: HTML

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

 

5

Law of Total Probability, Conditional Independence; The Base Rate Fallacy

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: textbook § 2 , except you may skip 2.1.4.

Be sure to 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.

Optional:

MCS § 14.1 - 14.7 is a rather more advanced treatment of the same materal.

 

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

HW 03: IPYNB

MarkdownTutorial: IPYNB

6 Combinations and "N choose K"; Applications to probability problems. Poker hands will be used to illustrate these counting principles.

Lecture Slides: PDF

Required: Finish reading from last time.

Optional: Secrets of Pascal's Triangle

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

 
7 Using combinations to count partitions; ordered partitions vs. unordered partitions; overcounting due to duplicates among subsets.

Discrete Random Variables; Functions and Expressions of RVs;

Lecture Slides: PDF

Required: 3.1.1 - 3.1.4

MCS § 14.5 concerns powersets and counting subsets; ;

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

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

HW 04: IPYNB

LatexTutorial: IPYNB

8

Functions and expressions of random variables; Independent and conditional random variables.

Important Discrete Distributions: Bernoulli, Binomial, Geometric, Pascal (Negative Binomial), Cumulative Distribution Functions (CDFs)

Lecture Slides: PDF

Required: 3.1.4 - 3.1.5.

Lectures and Materials/Distributions Notebook: IPYNB (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

HW 05: IPYNB

9

Discrete Distributions concluded: Memory-less property of Geometric; Expected Value, Games

Lecture Slides: PDF

Required: 3.2.2

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

Distributions Notebook: IPYNB (you do not need to know any that we do not study in lecture).

10 Expectation concluded; paradoxes and problems with Expectation; Variance and Standard Deviation of RVs

Lecture Slides: PDF

Required: 3.2.2 and 3.2.4

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

 
11

Important Results on Variance: Convergence and Limit Theorems;

General (continuous) Random Variables; Importance of the CDF; Expected value and Variance;

Lecture Slides: PDF

Required (on limit theorems): 6.2.2

Required (continuous distributions): 4.1.0 - 4.1.2

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

12

Continuous Distributions: General Principles concluded; Uniform Distribution; Geometric Probability

Lecture Slides: PDF

Brief Review of Integration (YouTube): YT

Required (special continuous distributions): 4.2.1 - 4.2.3

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

 
13

Normal Distribution and the Normal approximation to the Binomial; the Continuity Correction; The Central Limit Theorem (if time).

Lecture Slides: PDF

Jupyter notebook on CLT IPYNB

Required (special continuous distributions): 4.2.1 - 4.2.3

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

14 Applications of the CLT: Sampling, Confidence Intervals, and Hypothesis Testing

Lecture Slides: PDF

 
15

Exponential Distribution: Relationship to Geometric; Memoryless property;

Lecture Slides: PDF

Required (special continuous distributions): 4.2.1 - 4.2.3

Required: 11.1.0 - 11.1.2

 
16 Poisson Process: Counting processes, Poisson (Discrete) Distribution, relationship between Poisson and Exponential. Applications to Waiting Time problems.

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.

17

Introduction to Simulation Experiments; Discrete-Event Simulation; Queueing Theory

Lecture Slides: PDF

Viewings: Simple: simple; more complex

18 Joint Random Variables; Review of Independence

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

BU Day of Collective Engagement On Wednesday, June 24, BU will be holding a University-wide Day of Collective Engagement: Racism and Antiracism, Our Realities and Our Roles. This day-long event is designed to bring the BU community together to examine, learn, and reflect on racism in America.
19 Covariance, Correlation, and Autocorrelation

Lecture Slides: PDF

Notebook with Examples: IPYNB

Chapter 5.3.1  
20 Least Squares and Linear Regression

Lecture: PDF

Chapter 8.5

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

21 Machine Learning: Multiple Regression, Logistic Regression, and Naive Bayes Method.

Lecture Slides: A, B

  Final Exam

Final Exam: DOC, PDF,IPYNB

Table for standard normal distribution (will be provided on exam): 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