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. Each note may be covered in one or more lectures.

Megan says, “When I took the course, I studied the notes until I was able to comfortably reproduce all of the proofs.

• Note 0: Sets and Mathematical Notation
• Note 1: Propositional Logic
• Note 2: Proofs
• Note 3: Induction
• Note 4: Stable Matching
• Note 5: Graph Theory
• Note 6: Modular Arithmetic
• Note 7: Modular Arithmetic: FLT, RSA
• Note 8: Polynomials and Secret Sharing
• Note 9: Error Correcting Codes
• Note 10: Counting
• Note 11: Countability
• Note 12: Computability
• Note 13: Introduction to Discrete Probability
• Note 14: Conditional Probability, Independence, and Combinations of Events
• Note 15: Random Variables
• Note 16: Variance and Covariance
• Note 17: Concentration Inequalities
• Note 18: Applications
• Note 19: Geometric and Poisson Distributions
• Note 20: Estimation

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 0a: Introduction, Logic (solution)
• Discussion 0b: Proofs (solution)
• Discussion 1a: Induction (solution)
• Discussion 1b: Stable Matching (solution)
• Discussion 2a: Graphs I (solution)
• Discussion 2b: Graphs II (solution)
• Discussion 3a: Modular Arithmetic I (solution)
• Discussion 3b: Modular Arithmetic II (solution)
• Discussion 4a: RSA (solution)
• Discussion 4b: Polynomials, Secret Sharing (solution)
• Discussion 5a: Error Correcting Codes (solution)
• Discussion 5b: Counting I (solution)
• Discussion 6a: Counting II (solution)
• Discussion 6b: Countability (solution)
• Discussion 7a: Computability (solution)
• Discussion 8a: Intro to Discrete Probability (solution)
• Discussion 8b: Combination of Events and Bayes Rule (solution)
• Discussion 9a: Conditional Probability and Independence (solution)
• Discussion 9b: Random Variables (solution)
• Discussion 10a: Expectation (solution)
• Discussion 10b: Variance, Concentration Inequalities, and Weak Law of Large Numbers (solution)
• Discussion 11a: Geometric and Poisson Distributions, Confidence Intervals, Estimation (solution)
• Discussion 11b: Conditional Expectation

Homeworks

There will be weekly required homeworks, again designed to consolidate your understanding of the course material. It is highly recommended that you attempt all homeworks. Your lowest threes homework scores 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: Proofs and Induction (Sol)
• HW 2: Stable Matching and Graph Theory (Sol)
• HW 3: Graph Theory and Modular Arithmetic (Sol)
• HW 4: Modular Arithmetic and RSA (Sol)
• HW 5: Polynomials and Error Correcting Codes (Sol)
• HW 6: Counting (Sol)
• HW 7: Countability and Computability (Sol)
• HW 8: Intro to Discrete Probability (Sol)
• HW 9: Expectation, Conditional Probability, Bayes' Rule (Sol)
• HW 10: Random Variables, Distributions (Sol)
• HW 11: Confidence Intervals, Conditional Expectation, and Linear Regression

(Tentative) Lecture Schedule

• Lecture 1 : Introduction & Logic. Slides: (full) (6up) ( Note 1)
• Lecture 2 : Proofs, maybe induction. Slides: (full) (6up) ( Note 2 Note 3)
• Lecture 2 : Proofs, maybe induction. Slides: (full) (6up) ( Note 2 Note 3)
• Lecture 3 : Induction. Slides: (full) (6up) ( Note 3)
• Lecture 4 : Stable Matching. Slides: (full) (6up) ( Note 4)
• Lecture 5 : Graphs. Slides: (full) (6up) ( Note 5)
• Lecture 6 : Graphs. Slides: (full) (6up) ( Note 5)
• Lecture 7 : Finish Graphs, Modular Arithmetic. Slides: (full) (6up) ( Note 6)
• Lecture 8 : Modular Arithmetic: Extended gcd, CRT, FLT. Slides: (full) (6up) ( Note 6 Note 7)
• Lecture 9 : Cryptography. Slides: (full) (6up) ( Note 7)
• Lecture 10 : Polynomials. Slides: (full) (6up) ( Note 8)
• Lecture 11 : Error Correction. Slides: (full) (6up) ( Note 9)
• Lecture 12 : Counting. Slides: (full) (6up) ( Note 10)
• Lecture 13 : Counting/Midterm Review. Slides: (full) (6up) ( Note 10)
• Lecture 14 : Countability. Slides: (full) (6up) ( Note 11)
• Lecture 15 : Computability. Slides: (6up) ( Note 12)
• Lecture 16 : Introduction to Probability. Slides: (6up) ( Note 13)
• Lecture 17 : Conditional Probability, Independence, Bayes Rule. Slides: (6up) ( Note 14)
• Lecture 18 : Bayes Rule, Mutual Independence, Collisions, Collecting. Slides: (6up) ( Note 14 Note 18)
• Lecture 19 : Random Variables. Slides: (6up) ( Note 15)
• Lecture 20 : Distributions, Expectation, and Independence. Slides: (6up) ( Note 15 Note 19)
• Lecture 21 : Variance, Concentration Inequalities, WLLN. Slides: (6up) ( Note 16 Note 17)
• Lecture 22 : Confidence Intervals, Linear Regression. Slides: (6up) ( Note 17 Note 20)