Fall, 2018







Lecture 
Date 
Lecture & Lab Topics 
Readings Prob = "Schaum's Outline of Probability" MCS = "Mathematics for Computer Science" 
Practice Problems, Homeworks, and Tests 
Labs 
1  T 9/4  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. Lecture Slides: PDF 
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/6  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 through Ch. 1 & 2 in Prob if you need a review of the basic math background. Prob Sections 3.1  3.5. 
Practice problems from Prob (not to hand in): 3.2, 3.3, 3.5, 3.6, 3.7, 3.16, 3.18, 3.26. HW 01: IPYNB: due Th 9/13 @ midnight HW 01 Solution: PDF 

M 9/10 
Lab 01: IPYNB (Jupyter Notebook  right click and select Save Link As...). Due Th 9/13 @ midnight along with HW 01. Lab 01 Solution: PDF 

3  T 9/11  Set operations on events and axiomatic method for proving theorems about probability functions; nonequiprobable 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/13  Problem solving strategies; analysis using tree diagrams and the "Four Step Method"; the inverse method. Example: The Monty Hall Problem. Conditional Probability; Independence. 
Prob, Ch.4. 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 HW 02: ZIP (due 9/20 @ 11:59pm)


M 9/10 
Lab 2 Problem Set: ZIP 

5  T 9/18  Independence reviewed; Bayes' Rule. Counting principles and combinatorics; inclusionexclusion; counting as sampling and constructing outcomes. Selection with and without replacement; permutations; counting sets vs sequences; Lecture Slides: PDF 
Look at this summary of problemsolving 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. The second chapter of Prob has a brief treatment of these topics as well. Bayes' Rule is covered well in Prob pp.9091, including a nice explanation in terms of trees. The form of Bayes' Rule in Prob p.90 is very general; we will discuss only the simple case P(BA). Prob p. 9 and MCS 14.9 discuss the inclusionexclusion principle. Prob discusses random sampling briefly on p.38.

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


6  Th 9/20  Review: overcounting due to duplicates; multinomial coefficients; applications to finite probability problems.  Much of this should be review from CS 131! 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 

M 9/24  Here is an excellent short YT video on the basics of Poker: YT Lab 3: 

7  T 9/25  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; the Wiki article section on 5card 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 

8  Th 9/27  Discrete Random Variables; Functions of RVs; Distributions; Cumulative Distribution Functions.  Read Prob 5.1  5.3  Practice problems from Prob (not to hand in): 5.1  5.5, 5.8, 5.9 HW 04: HTML 

M 10/1  Lab 4: Generating Random Variates HTML  
9  T 10/2  Expected value, Variance, and Standard Deviation of RVs; Fair games  Read 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


10  Th 10/4  Important Discrete Distributions: Uniform, Bernoulli, Binomial; 
In Prob the Bernoulli and Binomial are explained in greater depth on pp.17780, and the Geometric on p.195. Here is a summary of some of the most useful discrete distributions: 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 
Practice problems from Prob (not to hand in): 6.2, 6.3, 6.5, 6.8, 6.12. HW 5: HTML Solution: PDF 

T 10/9  Monday schedule: Labs will be held but no lecture!  Lab 5: Bitcoin Lab: HTML  
11  Th 10/11  Discrete Distributions concluded: Geometric; Memoryless property of Geometric; Poisson Processes and Poisson Distribution; relationship between Poisson and Binomial. 
On Poisson Distribution: Prob section 6.7. Reading on the Poisson Processes: HTML 
Practice problems from Prob: 6.39, 6.43, plus look at Ex.6.19 on p.198. HW 06: HTML Solution: PDF 

M 10/15  Lab 6: Bitcoin Lab II: HTML Bitcoin Data for lab: CSV 

12  T 10/16  General (continuous) Random Variables; Uniform Distribution; Importance of CDF; 
Prob: 5.10, 5.11, 6.8 Brief tutorial on integration: PDF Prob Ch. 5: PDF Prob Ch. 6: PDF

Practice problems from Prob: 5.12, 5.37


13  Th 10/18  Exponential distribution; Memoryless property of Exponential Distribution; Relationship between the Exponential and Poisson Distribution. 
Prob:6.3, 6.4, & 6.5 Lecture on Normal Distribution: PDF 
Practice problems from Prob: 6.22, 6.23, 6.26, 6.28, 6.30 

M 10/22  Lab: Problem Solving Session (review for Midterm)


14  T 10/23  Normal Distribution and its relationship to Binomial  Practice problems from Prob: 6.33, 6.34 

W 10/24  Review Session for Midterm (location TBA)  Sample Midterms: PDF1, PDF2, PDF3, PDF4  
15  Th 10/25  Midterm Exam (Data Tentative)  HW 07: HTML Solution: PDF 

M 10/29  Lab 7: Bloom Filters: IPYNB  
16  T 10/30  Central Limit Theorem  The CLT is stated on p.189 of Prob. Not much discussion. Here is a reasonable tutorial, with videos: HTML 

17  Th 11/1  Basic Statistics: Sampling theory, point estimation, confidence intervals. 
Read Prob, Appendix A1  A4 (up to p.251) or PandS pp.153156, 1956, & 198. 
HW 08: HTML Solution: IPYNB 

M 11/5  Lab 8: ZIP Verifying the CLT and basic stats Here is documentation on the scipy.norm statistics library: HTML 

18  T 11/6  Sampling theory when population parameters are unknown, confidence intervals continued; Hypothesis Testing introduced  On Hypothesis Testing, here is a nice summary of the major points, with a video lecture: HTML  Here is a Jupyter notebook with various statistical functions for performing calculations: IPYNB 

19  Th 11/8  Hypothesis Testing continued; Power of a test.  HW 09: HTML Solution: IPYNB 

M 11/12  Lab 9: Queueing Simulation, Analyzing Statistical Data from a Simulation: ZIP  
20  T 11/13  ChiSquared tests for goodness of fit between theoretical and experiment distributions.  Read Appendix B from Prob on ChiSquared.  
21  Th 11/15  Joint Random Variables; Independence of JRVs; Correlation of JRVs  Read Schaum's 5.6  5.7, but correct the bad typo in the definition of correlation at the bottom of page 130: ρ(X,Y) = cov(X,Y) / (σ_{X}σ_{Y}) Here is my spreadsheet from lecture: XLS 

M 11/19  No lab  
22  T 11/20  Meaning of Correlation; Least squares and linear Regression 
Read Prob, Appendix A.6. 


Thanksgiving Recess  HW 10: ZIP Solution: ZIP 

M 11/26  Lab 10: Autocorrelation of Musical Signals IPYNB 

23  T 11/27  Regression: Linear Models 
I will follow closely the treatment in sections 1.4, 1.5, 1.6, 1.9 in this link. 

24  Th 11/29  Linear Models continued  No more homeworks!  
M 12/3  Final Project: IPYNB Dataset for project: CSV 

25  T 12/4  Logistic Regression  Video 1 (simpler, first of series of 5) Video 2 (more detailed) 

26  Th 12/6  Logistic Regression concluded; Perspectives on Machine Learning  Summary of Logistic Regression: HTML  
M 12/10  No Lab  
27  T 12/11  Conclusions; Review for Final Exam; Course Evaluations  
F 12/14  Final Project Due @ 12 midnight  
M 12/17  Office Hours and Review for Final  
T 12/18  Final Exam: 12:30  2:30pm  Table for standard normal distribution (will be provided on exam): PDF 