# Sections 01 & 02, Fall, 2020

Here is a brief summary of what was covered each day, along with an indication of what I plan to cover in the next lecture.
Frequently, I list the chapters and sections of the various textbooks that are most relevant.

• Sept. 1: Administrivia, Review of set theory, induction, countability. Random experiments, sample spaces, events, the Birthday problem ([LLM: 8.1, 17.1-2], [Ross: 2.2]).
• Sept. 3: More on sample spaces and events; the Monty Hall example [LLM 17.1-2]; Conditional Probability [LLM: 18.1-4][Ross: 3.1-2]
• Sept. 10: Bayes' Rule [LLM: 18.4], [Ross: 3,3] Start of Counting (Growth rate of the factorial function and Stirling's Formula) [LLM: Chapter 15], [Ross: Chapter 1]
• Sept. 15: Questions about homework. Start of Counting [LLM: Chapter 15], [Ross: Chapter 1] (Product Rule, Sum Rule, Division Rule, Binomial Coefficients)
• Sept. 17: Binomial Coefficients and the Binomial Theorem, Probabilities of various card hands, Multinomial Coefficients, Start of Inclusion-Exclusion [LLM: Chapter 15], [Ross: Chapter 1]
• Sept. 22: There was a quiz. Questions about Homework Assignment #2. Newton's generalized binomial theorem, generalized binomial coefficients, More on Inclusion-Exclusion [LLM: Chapter 15], [Ross: Chapter 1]
• Sept. 24: More on Inclusion-Exclusion, Derangements, Pigeonhole Principle, [LLM: Chapter 15], [Ross: Chapter 1] Independence [LLM 18.7][Ross: 3.4] Simpson's Paradox [LLM 18.6]
• Sept. 29: More on independence (and the case of People v. Collins (see also this account), odds, Bayes update factor [LLM 18.7 - 18.9][Ross Chapter 3]
• Oct. 1: Random variables, partitions of the sample space, frequency functions = Probability Density Functions, Bernoulli trials, Binomial Distribution, Geometric Distribution [LLM 19.1-2][Ross 4.1, 4.2, 4.6]
• Oct. 6: Expected Value, linearity of expectation, expected value of the binomial distribution, [LLM 19.4, 19.5.3][Ross 4.3, 4.6] Midterm exam will be available.
• Oct. 8: Expected Value of the geometric and negative binomial distributions, the method of indicators, [LLM 19.4, 19.5][Ross 4.3, 4.6] Midterm exam will be due.
• Oct. 13: Expectation of Independent Random Variables, Coupon Collecting, a gambling paradox, Markov's inequality, Variance, Covariance, Uncorrelated Random Variables [LLM, 19.5,20][Ross 4.5, 4.6, 4.8]
• Oct. 15: Properties of Variance, Standard Deviation, Variance of the geometric, negative binomial, and binomial random variables, Tchebycheff's Inequality [LLM 20][Ross, 4.5, 4.6, 4.8, 7.4, 7.5, 8.2]
• Oct. 20: Voter polls, Chernoff Bounds [LLM 20][Ross 7.2, 8.2, 8.5] Polynomial Identity Testing and the Schwartz-Zippel Lemma.
• Oct. 22: More on probabilistic algorithms. Sample Mean, The Law of Large Numbers, [LLM 20][Ross 7.2, 8.2, 8.5]
• Oct. 27: Confidence, Generating Functions, Solving recurrences [LLM 16]
• Oct. 29: Generating Functions, Solving recurrences [LLM 16]
• Nov. 3: Generating Functions, Continued. The ring of Formal Power Series. Convolution. Conbinatorial identity proofs via Generating Functions. Expectation and Variance via Generating Functions. [LLM 16]
• Nov. 5: This lecture was pre-recorded; no "live" lecture. Nore on Expectation and Variance via Generating Functions. Use of generating functions for counting the number of n-node binary trees. [LLM 16]
• Nov. 10: 2nd midterm will be available. Random Walks. Bertrand's Ballot Theorem [LLM 21]
• Nov. 12: 2nd midterm due. Random Walks. The Expected time to win \$1 for gamblers with unlimited credit [LLM 21]
• Nov. 17: Random Walks. Gamblers with limited credit [LLM21] Eulerian Paths, Basic Definitions about Graphs, Paths, and Walks [LLM10]
• Nov. 19: More on Eulerian Paths, and Hamiltonian Paths, Bipartite Graphs and Matchings [LLM 12.5]
• Nov. 24: Questions about Homework #8. Matchings and Hall's Theorem [LLM 12.5]
• Dec. 1: Graph Coloring, 2-colorable graphs and odd cycles [LLM 12.8] Planar Graphs; Euler's formula; The complete graph on 5 vertices is not planar. [LLM 13]
• Dec. 3: More on planar graphs; Proof that Euler's formula is correct. Polyhedra [LLM 13]
• Dec. 8: 5-coloring planar graphs [LLM 13], Google's page-rank algorithm and random walks [LLM 21.2].
• Dec. 10: Review.
• Dec. 15: Take-home final exam will be due.