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 Piazza Gradescope Textbook Web Site Snyder YouTube Channel Syllabus Python resources for CS 237 Fast demo of Jupyter Notebooks Complete YouTube tutorial on same Summary of Keyboard Shortcuts for Notebooks Homework Submission Instructions Comprehensive Introduction to Latex: YT CS 237 Data Repository: DIR CS 237 Tutorials Directory: DIR
 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