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: Sets
• Note 2: Propositional Logic
• Note 3: Proofs
• Note 4: Induction
• Note 5: Stable Matching
• 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: Computability
• Note 13: Introduction to Discrete Probability
• Note 14: Conditional Probability, Inclusion-Exclusion, Union Bound
• Note 15: Random Variables, Expectation
• Note 16: Variance, Covariance, Correlation
• Note 17: Concentration Inequalities, Law of Large Numbers
• Note 18: Hashing, Load Balancing (Optional)
• Note 19: Geometric, Poisson Distributions

Discussions

The discussion sections are specifically designed to consolidate the material covered in lectures and in the notes. It is highly recommended that you attend both discussions each week. You may attend any discussion section, but we recommend that you settle on a weekly two-section pair (with the same TA) as early as possible in the semester. If a particular section is too full, then students will be admitted on a first-come first-served basis and others will have to attend an alternative section. All sections are equivalent: they all cover the same material. See Policies for more information.

• Discussion 0A: Propositional Logic (solution)
• Discussion 0B: Proofs (solution)
• Discussion 0C-Quiz: Quiz (Logic, Proofs) (solution)
• Discussion 10A: Geometric Distribution
• Discussion 1A: Induction (solution)
• Discussion 1B: Stable Matching (solution)
• Discussion 2A: Stable Matching (solution)
• Discussion 2B: Graphs (solution)
• Discussion 3A: Modular Arithmetic (solution)
• Discussion 3B: Fermat's Little Theorem, Bijections (solution)
• Discussion 4A: RSA (solution)
• Discussion 4B: Polynomials (solution)
• Discussion 5A: Polynomials, Secret Sharing (solution)
• Discussion 5B: Error Correction (solution)
• Discussion 6A: Counting (solution)
• Discussion 6B: Counting, Combinatorial Proof (solution)
• Discussion 7A: Countability, Computability (solution)
• Discussion 7B: Probability (solution)
• Discussion 8A: Probability (solution)
• Discussion 8B: Probability (solution)
• Discussion 9A: Discrete Probability Distributions (solution)
• Discussion 9B: Expectation (solution)

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 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 0: Course Logistics, Background (Sol)
• HW 1: Propositional Logic, Proofs (Sol) (Self Grades)
• HW 10: Expectation, Probability, Discrete Distributions
• HW 2: Induction, Stable Matching (Sol) (Self Grades)
• HW 3: Stable Matching, Modular Arithmetic (Sol) (Self Grades)
• HW 4: Modular Arithmetic (Sol) (Self Grades)
• HW 5: RSA, Polynomials, Secret Sharing (Sol) (Self Grades)
• HW 6: Error Correcting Codes (Sol) (Self Grades)
• HW 7: Probability, Countability, Computability, Counting (Sol) (Self Grades)
• HW 8: Counting, Discrete Probability (Sol) (Self Grades)
• HW 9: Discrete Probability (Sol) (Self Grades)
• HW Midterm1: Midterm1 Redo (Sol) (Self Grades)

Lecture Schedule

• Lecture 0A (1/21): Introduction & Logic (Note 0Note 1Note 2)
• Lecture 0B (1/23): Proofs (Note 3)
• Lecture 1A (1/28): Induction (Note 4)
• Lecture 1B (1/30): Stable Matching (Note 5)
• Lecture 2A (2/4): Stable Matching (Note 5)
• Lecture 2B (2/6): Graphs (Note 6)
• Lecture 3A (2/11): Modular Arithmetic (Note 7)
• Lecture 3B (2/13): Bijections/FLT, CRT (Note 7Note 8)
• Lecture 4A (2/18): RSA, Polynomials (Note 8)
• Lecture 4B (2/20): Polynomials, Secret Sharing (Note 9)
• Lecture 5A (2/25): Secret Sharing, Error Correcting Codes (Note 9Note 10)
• Lecture 5B (2/27): Polynomials, Secret Sharing (Note 10)
• Lecture 6A (3/3): Counting (Note 11)
• Lecture 6B (3/5): Counting II (Note 11)
• Lecture 7A (3/10): Computability, Counting (Note 12)
• Lecture 7B (3/12): Intro to Discrete Probability (Note 13)
• Lecture 8A (3/17): Inclusion-Exclusion, Conditional Probability (Note 14)
• Lecture 8B (3/19): Conditional Probability, Union Bound (Note 14Note 18)
• Lecture 9A (3/31): Random Variables, Discrete Probability Distributions (Note 15Note 19)
• Lecture 9B (4/2): Random Variables, Expectation (Note 15Note 19)
• Lecture 10A (4/7): Review (Note 15Note 19)
• Lecture 10B (4/9): Expectation, Variance (Note 15Note 19)