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 -1: Intro to CS70
• 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 5.5: Graphs II
• Note 6: Modular Arithmetic
• Note 6.5: Chinese Remainder Theorem, Fermat's Little Theorem
• 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 12.5: Counting II
• Note 13: Introduction to Discrete Probability
• Note 14: Conditional Probability
• Note 15: Discrete Random Variables: Intro and Distribution
• Note 15.5: Random Variables: 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 b1: Bonus Note 1
• Note b2: Bonus Note 2
• Note b3: Bonus Note 3

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 (solution)
• Discussion 01d: Graphs (solution)
• Discussion 02a: Graphs (solution)
• Discussion 02b: Modular Arithmetic (solution)
• Discussion 02c: Modular Arithmetic, Bijections (solution)
• Discussion 03a: RSA (solution)
• Discussion 03b: Polynomials (solution)
• Discussion 03c: Error Correcting Codes (solution)
• Discussion 03d: Countability (solution)
• Discussion 04a: Computability (solution)
• Discussion 04b: Counting I (solution)
• Discussion 04c: Counting II (solution)
• Discussion 04d: Introduction to Probability (solution)
• 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) (Sol)
• HW 01: Propositional Logic, Proofs, Induction (TeX) (Sol)
• HW 02: Graphs, Modular Arithmetic (TeX) (Sol)
• HW 03: RSA, Polynomials, Countability (TeX) (Sol)
• HW 04: Computability, Counting, Intro to Probability (TeX) (Sol)
• HW 05: Conditional Probability, Random Variables, Discrete Distributions (TeX)
• 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 -1Note 0Note 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 (full) (6up) (Note 5)
• Lecture bonus1 (6/28): Extra Topics: Formal Proof Systems (full) (6up) (Note b1)
• Lecture 5 (7/01): Graphs II (full) (6up) (Note 5.5)
• Lecture 6 (7/02): Modular Arithmetic (full) (6up) (Note 6)
• Lecture 7 (7/03): Modular Arithmetic(FLT, CLT), Bijections (full) (6up) (Note 6Note 6.5)
• Lecture bonus2 (7/05): Extra Topics: Euler's Totient Function (full) (6up) (Note b2)
• Lecture 8 (7/08): RSA/Cryptography (full) (6up) (Note 7)
• Lecture 9 (7/09): Polynomials (full) (6up) (Note 8)
• Lecture 10 (7/10): Error Correcting Codes (full) (6up) (Note 9)
• Lecture 11 (7/11): Countability (full) (6up) (Note 10)
• Lecture bonus3 (7/12): Cantor-Schroder-Bernstein (full) (6up) (Note b3)
• Lecture 12 (7/15): Computability (full) (6up) (Note 11)
• Lecture 13 (7/16): Counting, Combinatorial Proofs I (full) (6up) (Note 12)
• Lecture 14 (7/17): Counting, Combinatorial Proofs II (full) (6up) (Note 12.5)
• Lecture 15 (7/18): Probability Space, Complements, Symmetry, Birthday / Monty Hall (full) (6up) (Note 13)
• Lecture bonus4 (7/19): The Catalan Numbers (full) (6up) ()
• Lecture 16 (7/22): Conditional Probability, Total Probability Theorem, Bayes Rule (full) (6up) (Note 14)
• Lecture 17 (7/23): Independence, Unions, Intersections, Inclusion-Exclusion (full) (6up) (Note 13Note 14)
• Lecture 18 (7/24): Random Variables, Bernoulli, Binomial, Geometric, Poisson (Note 15)
• Lecture 19 (7/25): Joint PMF, Independence, Expectation of Random Variables, Linearity (Note 15.5)
• Lecture Extra (7/26): Hashing and Load Balancing (Note 17)
• Lecture 20 (7/29): Expectation Continued: Tail Sum Bound, Geometric, Poisson, Coupon Collector (Note 15.5Note 19)
• Lecture 21 (7/30): Variance, Covariance, Geometric, Poisson (Note 16Note 19)
• Lecture 22 (7/31): Chebyshev Inequalities, Confidence Intervals, Law of Large Numbers (Note 18)
• Lecture 23 (8/01): Continuous RV, PDF, CDF, Joint CDF, Uniform, Exponential (Note 20)
• Lecture Extra (8/02): Poisson Processes ()
• Lecture 24 (8/05): Normal RVs, Conditional PDF, Central Limit Theorem, Buffon's Needle (Note 20)
• 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 21)
• Lecture Extra (8/09): PageRank ()
• 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 ()