Introduction to Discrete Structures II
198:206
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.