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

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 00a: Propositional Logic (solution)
• Discussion 00b: Proofs (solution)
• Discussion 01a: Induction (solution)
• Discussion 01b: Stable Marriage (solution)
• Discussion 02a: Graphs I (solution)
• Discussion 02b: Graphs II (solution)
• Discussion 03a: Modular Arithmetic I (solution)
• Discussion 03b: Modular Arithmetic II (solution)
• Discussion 04a: RSA (solution)
• Discussion 05a: Polynomials, Secret Sharing (solution)
• Discussion 05b: Error-Correcting Codes (solution)
• Discussion 06a: Countability, Computability (solution)
• Discussion 06b: Counting I (solution)
• Discussion 07a: Counting II (solution)
• Discussion 07b: Introduction to Probability (solution)
• Discussion 08a: Conditional Probability (solution)
• Discussion 08b: Inclusion - Exclusion (solution)
• Discussion 09a: Random Variables I (solution)
• Discussion 09b: Random Variables II (solution)
• Discussion 10a: Geometric and Poisson Random Variables (solution)
• Discussion 10b: Joint and Condition PMFs (solution)
• Discussion 11a: Continuous Random Variables (solution)
• Discussion 11b: Joint and Conditional PDFs (Continuous) (solution)
• Discussion 12a: Normal Distribution (solution)
• Discussion 12b: Inequalities, Law of Large Numbers (solution)
• Discussion 13a: Markov Chains I (solution)
• Discussion 13b: Markov Chains II, Fun (solution)

Homeworks

Homeworks are graded for accuracy and it is highly recommended that you do them. Your lowest two homework scores will be dropped, but these drops 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 (TeX) (Sol)
• HW 02: Induction, Stable Marriage (TeX) (Sol)
• HW 03: Graphs, Modular Arithmetic (TeX) (Sol)
• HW 04: Modular Arithmetic (TeX) (Sol)
• HW 05: RSA, Secret Sharing (TeX) (Sol)
• HW 06: Error Correcting, Countability, Computability (TeX) (Sol)
• HW 07: Counting (TeX) (Sol)
• HW 08: Probability, Conditional Probability (TeX) (Sol)
• HW 09: Union Bound, Hashing, Inclusion-Exclusion, Random Variables (TeX) (Sol)
• HW 10: Variance, Joint Distributions (TeX) (Sol)
• HW 11: Joint Distributions, Continuous Random Variables (TeX) (Sol)
• HW 12: Joint Continuous and Conditional Probability, Normal Distribution (TeX) (Sol)
• HW 13: Concentration Inequalities, CLT, Markov Chains (TeX) (Sol)

Lecture Schedule

• Lecture 1 (1/22): Introduction, Propositional Logic, First-Order Logic (full) (6up) (Note 1)
• Lecture 2 (1/24): Proof: The Basics and a bit of Induction (full) (6up) (Note 2)
• Lecture 3 (1/29): More Induction (full) (6up) (Note 3)
• Lecture 4 (1/31): Stable Marriage (full) (6up) (Note 4)
• Lecture 5 (2/5): Graphs (full) (6up) (Note 5)
• Lecture 6 (2/7): More Graphs (full) (6up) (Note 5)
• Lecture 7 (2/12): Modular Arithmetic (full) (6up) (Note 6)
• Lecture 8 (2/14): Fermat/CRT/ Begin RSA (full) (6up) (Note 7)
• Lecture 9 (2/19): RSA/ Midterm Review (full) (6up) (Note 7)
• Lecture 10 (2/26): Polynomials (full) (6up) (Note 8)
• Lecture 11 (2/28): Polynomials:Error Correction (full) (6up) (Note 9)
• Lecture 12 (3/5): Countability/Undecidability (full) (6up) (Note 10Note 11)
• Lecture 13 (3/7): Undecidability/Counting (full) (6up) (Note 11)
• Lecture 14 (3/12): Counting (full) (6up) (Note 12)
• Lecture 15 (3/14): Introduction to Discrete Probability (Note 13)
• Lecture 16 (3/19): Conditional Probability (Note 14)
• Lecture 17 (3/21): Conditional Probability, Union Bound (Note 14Note 17)
• Lecture 18 (4/2): Random Variables I (Note 15Note 19)
• Lecture 19 (4/4): Random Variables II (Note 15Note 19)
• Lecture 20 (4/9): Geometric Distribution, Coupon Collector, Poisson Distirbution, Variance (Note 16Note 19)
• Lecture 21 (4/11): Joint and Conditional PMFs, Applications, Introduction to Continuous (Note 15Note 19)