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: Introduction
• Note 1: Logic
• Note 2: Proofs
• Note 3: Induction
• Note 4: Sets and Functions
• Note 5: Cardinality and Computability
• Note 6: Graph Theory
• Note 7: Modular Arithmetic
• Note 8: Public Key Cryptography (RSA)
• Note 9: Polynomials
• Note 10: Error Correcting Codes
• Note 11: Counting
• Note 12: Introduction to Probability
• Note 13: Conditional Probability, Inclusion-Exclusion, Union Bound
• Note 14: Random Variables
• Note 15: Variance, Covariance, Correlation
• Note 16: Distributions
• Note 17: Concentration Inequalities, Law of Large Numbers
• Note 20: Continuous Probability
• Note 24: Markov Chains

Discussions

Discussions will be held over Zoom. The discussion sections are specifically designed to consolidate the material covered in lectures and in the notes. It is highly recommended that you attend all discussions each week. You should attend the discussion that you signed up for, since attendance for that discussion will be graded. All sections are equivalent: they all cover the same material. See Policies for more information.

• Discussion 1A: Introduction, Logic (solution)
• Discussion 1B: Proofs (solution)
• Discussion 1C: Induction (solution)
• Discussion 1D: Sets and Functions (solution)
• Discussion 2A: Countability and Computability (solution)
• Discussion 2B: Graphs 1 (solution)
• Discussion 2C: Graphs 2 (solution)
• Discussion 2D: Modular Arithmetic 1 (solution)
• Discussion 3A: Modular Arithmetic 2 (solution)
• Discussion 3B: RSA (solution)
• Discussion 3C: Polynomials and Secret Sharing (solution)
• Discussion 3D: Error Correcting Codes (solution)
• Discussion 4A: Counting 1 (solution)
• Discussion 4B: Counting 2 and Combinatorial Proof (solution)
• Discussion 4C: Intro to Probability (solution)
• Discussion 5A: Conditional Probability (solution)
• Discussion 5B: Independence, Combination of Events, Inclusion-Exclusion, Union Bound (solution)
• Discussion 5C: Discrete Random Variables (solution)
• Discussion 5D: Variance, Covariance (solution)
• Discussion 6A: Geometric and Poisson (solution)
• Discussion 6B: Continuous Probability Intro (solution)
• Discussion 6C: Continuous Distributions (solution)
• Discussion 6D: More Continuous Probability (solution)
• Discussion 7A: Probabilistic Bounds (solution)
• Discussion 7B: CLT and Confidence Intervals (solution)
• Discussion 7C: Markov Chains 1 (solution)
• Discussion 7D: Markov Chains 2 (solution)

Homeworks

There will be weekly required homeworks (9 total, including a Homework 0), again designed to consolidate your understanding of the course material. It is highly recommended that you attempt all homeworks. 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 0: Logistics and Review (Sol)
• HW 1: Logic, Proofs, Basic Structures (Sol)
• HW 2: Countability and Computability, Graphs, Modular Arithmetic Intro (Sol)
• HW 3: Modular Arithmetic 2, RSA Cryptography, Polynomials (Sol)
• HW 4: Counting and Intro to Probability (Sol)
• HW 5: Conditional Probability, Random Variables, Variance (Sol)
• HW 6: Geometric and Poisson, Continuous Probability and Distributions (Sol)
• HW 7: Confidence Intervals, Markov Chains (Sol)
• HW 8: Final Exam

Lecture Schedule

• Lecture 1A (6/22): Introduction & Logic (full)
• Lecture 1B (6/23): Proofs (full)
• Lecture 1C (6/24): Induction (full)
• Lecture 1D (6/25): Sets, Functions (full)
• Lecture 2A (6/29): Cardinality, Computability (full)
• Lecture 2B (6/30): Graphs 1 (full)
• Lecture 2C (7/1): Graphs 2 (full)
• Lecture 2D (7/2): Modular Arithmetic 1 (full)
• Lecture 3A (7/6): Modular Arithmetic 2 (full)
• Lecture 3B (7/7): RSA/Crytography (full)
• Lecture 3C (7/8): Polynomials and Secret Sharing (full)
• Lecture 3D (7/9): Error Correcting Codes (full)
• Lecture cancelled (7/13): Midterm
• Lecture 4A (7/14): Counting 1 (full)
• Lecture 4B (7/15): Counting 2 (full)
• Lecture 4C (7/16): Intro to Discrete Probability (full)
• Lecture 5A (7/20): Conditional Probability, Bayes' Rule, Total Probability Rule (full)
• Lecture 5B (7/21): Independence, Combination of Events, Inclusion-Exclusion, Union Bound (full)
• Lecture 5C (7/22): Discrete Random Variables (full)
• Lecture 5D (7/23): Variance and Covariance (full)
• Lecture 6A (7/27): Distributions (full)
• Lecture 6B (7/28): Intro to Continuous Probability (full)
• Lecture 6C (7/29): Continuous Distributions (full)
• Lecture 6D (7/30): Joint Distributions (full)
• Lecture 7A (8/3): Concentration Inequalities (full)
• Lecture 7B (8/4): Concentration Inequalities 2 (full)
• Lecture 7C (8/5): Markov Chains 1 (full)
• Lecture 7D (8/6): Markov Chains 2 (full)
• Lecture 8A (8/10): Prof Amir Yehudayoff - Bayes (10 AM) (Extra)
• Lecture 8B (8/11): Prof Satish Rao - Stable Marriage (Extra)
• Lecture 8C (8/12): Prof Nikhil Srivastava - Markov Chains (Extra)
• Lecture 8D (8/13): Instructor AMA (Extra)