Notes

There is no textbook for this class. Instead, there is a set of comprehensive lecture notes. Make sure you revisit the notes after every lecture, and multiple times thereafter: you should be aware that it will likely take several readings before you fully understand the material. Each note may be covered in one or more lectures. See Policies for more information.

• Note 0: Review of Sets, Notation
• Note 1: Propositional Logic
• Note 2: Proofs
• Note 3: Induction
• Note 4: Stable Marriage
• Note 5: Graph Theory
• Note 6: Modular Arithmetic
• Note 7: Public Key Cryptography
• Note 8: Polynomials
• Note 9: Error Correcting Codes
• Note 10: Infinity and Uncountability
• Note 11: Self-Reference and Uncomputability
• Note 12: Counting
• Note 13: Introduction to Discrete Probability
• Note 14: Conditional Probability
• Note 15: Random Variables: Distribution & Expectation
• Note 16: Random Variables: Variance & Covariance
• Note 17: Hashing and Load Balancing
• Note 18: Concentration Inequalities and LLN
• Note 19: Geometric and Poisson Distributions
• Note 20: Continuous Probability Distributions
• Note 21: Finite Markov Chains
• Note -1: Intro to CS70
• Note b1: Bonus Note 1

Discussions

The discussion sections will not cover new material, but rather will give you additional practice solving problems. You can attend any discussion section you like. However, if there are fewer desks than students, then students will be admitted to the section on a first-come first-served basis and others will have to attend an alternative section. See Policies for more information.

• Discussion 01a: Propositional Logic (solution)
• Discussion 01b: Proofs (solution)
• Discussion 01c: Induction
• Discussion 01d: Graphs
• Discussion 02a: Graphs
• Discussion 02b: Modular Arithmetic
• Discussion 02c: Modular Arithmetic, Bijections
• Discussion 02d:
• Discussion 03a: RSA
• Discussion 03b: Polynomials
• Discussion 03c: Error Correcting Codes
• Discussion 03d: Countability
• Discussion 04a: Computability
• Discussion 04b: Counting I
• Discussion 04c: Counting II
• Discussion 04d: Introduction to Probability
• Discussion 05a: Conditional Probability
• Discussion 05b: Independence, Inclusion Exclusion
• Discussion 05c: Random Variables I
• Discussion 05d: Random Variables II
• Discussion 06a: Variance, Conditional PMF
• Discussion 06b: Covariance
• Discussion 06c: Continuous Random Variables
• Discussion 06d: Joint and Conditional PDF
• Discussion 07a: Inequalities, CLT
• Discussion 07b: Markov Chains
• Discussion 07c: Hitting Time
• Discussion 07d: Markov Chains LLN

Homeworks

Homeworks are graded based on reasonable effort and not accuracy and it is highly recommended that you do them. What this means is that we will give you feedback and a numerical score so you know how you are doing in the class, but this score is not your grade. Instead, as long as you get some credit on a part, it will be counted as if you got full credit. Homework 0 is required for everyone but it will not count towards your grade. Your lowest homework score will be dropped, but this drop should be reserved for emergencies . No additional allowances will be made for late or missed homeworks: please do not contact us about missed homeworks or late submissions. See Policies for more information.

• HW 00: Course Logistics (TeX)
• HW 01: Propositional Logic, Proofs, Induction (TeX)
• Homework 02: Graphs, Modular Arithmetic
• Homework 03: RSA, Polynomials, Countability
• Homework 04: Computability, Counting, Intro to Probability
• Homework 05: Conditional Probability, Random Variables, Discrete Distributions
• Homework 06: Variance, Covariance, Continuous Random Variables
• Homework 07: Markov Chains
• Homework 08:

Lecture Schedule

• Lecture 1 (6/24): Introduction, Propositional Logic, Truth Tables (full) (6up) (Note 0Note 1Note -1)
• Lecture 2 (6/25): Proofs and Proof Methods (full) (6up) (Note 2)
• Lecture 3 (6/26): Induction (full) (6up) (Note 3)
• Lecture 4 (6/27): Graphs I (Note 5)
• Lecture Extra (6/28): Extra Topics: TBD (Note b1)
• Lecture 5 (7/01): Graphs II (Note 5)
• Lecture 6 (7/02): Modular Arithmetic (Note 6)
• Lecture 7 (7/03): Modular Arithmetic(FLT, CLT), Bijections (Note 6Note 7)
• Lecture Extra (7/05): Extra Topics: TBD ()
• Lecture 8 (7/08): RSA/Cryptography (Note 7)
• Lecture 9 (7/09): Polynomials (Note 8)
• Lecture 10 (7/10): Error Correcting Codes (Note 9)
• Lecture 11 (7/11): Countability (Note 10)
• Lecture Extra (7/12): Extra Topics: TBD ()
• Lecture 12 (7/15): Computability (Note 12)
• Lecture 13 (7/16): Counting, Combinatorial Proofs I (Note 12)
• Lecture 14 (7/17): Counting, Combinatorial Proofs II (Note 12)
• Lecture 15 (7/18): Probability Space, Complements, Symmetry, Birthday / Monty Hall (Note 13)
• Lecture Extra (7/19): Extra Topics: TBD ()
• Lecture 16 (7/22): Conditional Probability, Total Probability Theorem, Bayes Rule (Note 14)
• Lecture 17 (7/23): Independence, Unions, Intersections, Inclusion-Exclusion (Note 13Note 14Note 17)
• Lecture 18 (7/24): Random Variables, Probability Mass Function, Joint PMF, Bernoulli, Binomial, Geometric, Poisson RVs (Note 15Note 19)
• Lecture 19 (7/25): Expectation, Linearity, Bernoulli, Binomial, Geometric, Poisson RVs, Coupon Collector (Note 15Note 17Note 19)
• Lecture Extra (7/26): Extra Topics: TBD ()
• Lecture 20 (7/29): Variance, Conditional PMF, Independent RVs (Note 16)
• Lecture 21 (7/30): Variance, Covariance, Tail Sum Formula (Note 16)
• Lecture 22 (7/31): Continuous RV, Probability Density Function, Cumulative Distribution Function, Uniform, Exponential RVs (Note 20)
• Lecture 23 (8/01): Joint PDF, Conditional PDF, Normal RV (Note 20)
• Lecture Extra (8/02): Extra Topics: TBD ()
• Lecture 24 (8/05): Central Limit Theorem, Markov, Chebyshev Inequalities, Confidence Intervals, Law of Large Numbers (Note 18)
• Lecture 25 (8/06): Markov Chain Definition, Probability Of A Path, n-Step Transition Probabilities (Note 21)
• Lecture 26 (8/07): Hitting Times, Probability of A Before B (Note 21)
• Lecture 27 (8/08): Classification Of States, Law of Large Numbers for Markov Chains, Markov Chain Convergence Theorem (Note 15Note 19)
• Lecture Extra (8/09): Extra Topics: TBD ()
• Lecture 28 (8/12): Final Review (Discrete Math) ()
• Lecture 29 (8/13): Final Review (Probability Theory) ()
• Lecture 30 (8/14): Discrete Math: Stable Marriage (Note 4)
• Lecture 31 (8/15): Probability: TBD ()