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: 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: Public Key Cryptography (RSA)
• Note 8: Polynomials
• Note 9: Error Correcting Codes
• Note 10: Counting
• Note 11: Countability
• Note 12: Computability
• Note 13: Intro to Discrete Probability
• Note 14: Conditional Probability
• Note 15: Random Variables: Distribution and Expectation
• Note 16: Random Variables: Variance and Covariance
• Note 17: Concentration Inequalities
• Note 18: Applications
• Note 19: Geometric and Poisson Distributions
• Note 20: Continuous Distributions
• Note 21: 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 0: Introduction, Logic (solution)
• Discussion 01a: Proofs (solution)
• Discussion 01b: Induction (solution)
• Discussion 02a: Stable Matching (solution)
• Discussion 02b: Graphs I (solution)
• Discussion 03a: Graphs II (solution)
• Discussion 03b: Modular Arithmetic (solution)
• Discussion 04a: Modular Arithmetic (CRT) (solution)
• Discussion 04b: RSA (solution)
• Discussion 05a: Polynomials, Secret Sharing (solution)
• Discussion 05b: Error Correcting Codes (solution)
• Discussion 06a: Counting (solution)
• Discussion 06b: Counting II (solution)
• Discussion 08a: Countability (solution)
• Discussion 08b: Countability and The Halting Problem (solution)
• Discussion 09a: Intro to Probability (solution)
• Discussion 09b: Conditional Probability (solution)
• Discussion 10a: Conditional Probability (solution)
• Discussion 10b: Intro to Random Variables I (solution)
• Discussion 11a: Intro to Random Variables II (solution)
• Discussion 11b: Variance (solution)
• Discussion 12a: Concentration Inequalities, LLN (solution)
• Discussion 12b: Applications, Memoryless Property (solution)
• Discussion 13a: Intro to Continuous (solution)
• Discussion 14a: Continuous Probability
• Discussion 14b: Markov Chains

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 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: Logistics and Review (Sol)
• HW 01: Proofs and Induction (Sol)
• HW 02: Induction and Stable Matching (Sol)
• HW 03: Graphs (Sol)
• HW 04: Modular Arithmetic and RSA (Sol)
• HW 05: RSA and Secret Sharing (Sol)
• HW 06: Error Correcting Codes and Counting (Sol)
• HW 07: Counting (Sol)
• HW 08: Countability (Sol)
• HW 09: Complexity and Probability (Sol)
• HW 10: Probability (Sol)
• HW 11: Random Variables (Sol)
• HW 12: Variance, Concentration Inequalities (Sol)
• HW 13: Hashing, Memoryless, and Continuous
• HW 14: Continuous Probability
• Homework 15: Markov Chains

(Tentative) Lecture Schedule

• Lecture 1 : Introduction & Logic. Slides: (full) (6up) ( Note 1)
• Lecture 2 : Proofs. Slides: (full) (6up) ( Note 2)
• Lecture 3 : Induction. Slides: (full) (6up) ( Note 3)
• Lecture 4 : Stable Matching. Slides: (full) (6up) ( Note 4)
• Lecture 5 : Graphs I. Slides: (full) (6up) ( Note 5)
• Lecture 6 : Graphs II. Slides: (full) (6up) ( Note 5)
• Lecture 7 : Modular Arithmetic. Slides: (full) (6up) ( Note 6)
• Lecture 8 : Modular Arithmetic. Slides: (full) (6up) ( Note 6)
• Lecture 9 : CRT/FLT/Public Key. Slides: (full) (6up) ( Note 7)
• Lecture 10 : Polynomials/Secret Sharing. Slides: (full) (6up) ( Note 8)
• Lecture 11 : Errors: Erasures and Corrections. Slides: (full) (6up) ( Note 9)
• Lecture 12 : Counting I. Slides: (full) (6up) ( Note 10)
• Lecture 13 : Counting II/Midterm Review. Slides: (full) (6up) ( Note 10)
• Lecture : Midterm(no lecture)
• Lecture : Break
• Lecture 14 : Countability. Slides: (full) (6up) ( Note 11)
• Lecture 15 : Computability/Self Reference. Slides: (full) (6up) ( Note 12)
• Lecture 16 : Probability. Slides: (full) (6up) ( Note 13)
• Lecture 17 : Conditional Probability. Slides: (full) (6up) ( Note 13 Note 14)
• Lecture 18 : Combination of Events. Slides: (full) (6up) ( Note 14)
• Lecture 19 : Random Variables I. Slides: (full) (6up) ( Note 15 Note 19)
• Lecture 20 : Random Variables II. Slides: (full) (6up) ( Note 15 Note 19)
• Lecture 21 : Variance and Covariance.. Slides: (full) (6up) ( Note 16 Note 19)
• Lecture 22 : Concentration Inequalities and LLN. Slides: (full) (6up) ( Note 17)
• Lecture 23 : Applications. Memoryless Properties. Slides: (full) (6up) ( Note 18 Note 19)
• Lecture 24 : Continuous Distributions I. Slides: (full) (6up) ( Note 20)
• Lecture : Thanksgiving.
• Lecture 25 : Continuous Distributions II. (Draft) Slides: (full) (6up) ( Note 20)
• Lecture 26: Markov Chains