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.

When you read the notes, try covering up the proofs and examples and working through them yourself. Only continue reading the notes once you have either figured things out for yourself or gotten stuck. This will give you a much deeper understanding of the material than if you read passively.

• Note 0: Sets and Mathematical Notation
• Note 1: Propositional Logic
• Note 2: Proofs
• Note 3: Induction
• Note 4: Cardinality
• Note 5: Computability (optional)
• Note 6: Graph Theory
• Note 7: Modular Arithmetic
• Note 8: Public Key Cryptography
• Note 9: Polynomials
• Note 10: Error Correcting Codes (Optional)
• Note 11: Counting
• Note 12: Introduction to Probability
• Note 13: Conditional Probability
• Note 14: Random Variables
• Note 15: Variance and Covariance
• Note 16: More Distributions
• Note 17: Continuous Probability Distributions
• Note 18: Concentration Inequalities
• Note 19: 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. There will be three types of discussion sections: two large discussion sections per day which anyone may attend whenever they want to, a number of small discussion sections which you must sign up for, and pre-recorded discussion videos uploaded to YouTube. If you sign up for a small discussion section, make sure you attend it since TA hours are limited. All discussion sections will cover the same material. See Policies for more information.

• Discussion 01a: Introduction, Logic
• Discussion 01b: Intro to Proofs
• Discussion 01c: Induction, Strong Induction
• Discussion 01d: Sets, Functions and Cardinality
• Discussion 02a: Graphs and Planarity
• Discussion 02b: Modular Arithmetic 1
• Discussion 02c: Modular Arithmetic 2, CRT
• Discussion 03a: RSA
• Discussion 03b: Polynomials and Secret-Sharing
• Discussion 03c: Intro to Counting
• Discussion 04a: Counting and Combinatorial Proofs
• Discussion 04b: Intro to Probability
• Discussion 04c: Conditional Probability, Bayes' Rule
• Discussion 05a: Independence, Union Bound
• Discussion 05b: Random Variables, Linearity of Expectation
• Discussion 05c: Variance and Covariance
• Discussion 05d: Distributions
• Discussion 06a: Continuous Probability
• Discussion 06b: Continuous Distributions 1
• Discussion 06c: Continuous Distributions 2
• Discussion 06d: Joint Continuous Distributions
• Discussion 07a: Concentration Inequalities, Confidence Intervals
• Discussion 07b: Confidence Intervals, Law of Large Numbers, CLT
• Discussion 07c: Intro to Markov Chains
• Discussion 07d: Markov Chains 2

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 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 00: Logistics and Logic
• HW 01: Induction, Functions, and Graph Theory
• HW 02: Modular Arithmetic, RSA, Midterm Proctoring
• HW 03: Polynomials, Counting, Combinatorial Proofs
• HW 04: Discrete Probability, Conditional Probability
• HW 05: Continuous Probability & Distributions
• HW 06: Continuous Distributions, Concentration Inequalities, CLT
• HW 07: Markov Chains

Lecture Schedule

• Lecture 1A (6/21): Introduction & Logic. Slides: (blank) (full) (Note 1 )
• Lecture 1B (6/22): Proofs. Slides: (blank) (full) (Note 2 )
• Lecture 1C (6/23): Induction. Slides: (blank) (full) (Note 3 )
• Lecture 1D (6/24): Sets, Functions and Cardinality. Slides: (blank) (full) (Note 0 Note 4 Note 5 )
• Lecture Cancelled (6/28): Holiday
• Lecture 2A (6/29): Graphs. Slides: (blank) (full) (Note 6 )
• Lecture 2B (6/30): Modular Arithmetic 1. Slides: (blank) (full) (Note 7 )
• Lecture 2C (7/1): Modular Arithmetic 2. Slides: (blank) (full) (Note 7 )
• Lecture Cancelled (7/5): Holiday
• Lecture 3A (7/6): Cryptography. Slides: (blank) (full) (Note 8 )
• Lecture 3B (7/7): Polynomials. Slides: (blank) (full) (Note 9 )
• Lecture 3C (7/8): Counting 1. Slides: (blank) (full) (Note 11 )
• Lecture Cancelled (7/12): Midterm Exam
• Lecture 4A (7/13): Counting 2. Slides: (blank) (full) (Note 11 )
• Lecture 4B (7/14): Introduction to Probability. Slides: (blank) (full) (Note 12 )
• Lecture 4C (7/15): Conditional Probability. Slides: (blank) (full) (Note 13 )
• Lecture 5A (7/19): Independence. Slides: (blank) (full) (Note 13 )
• Lecture 5B (7/20): Random Variables. Slides: (blank) (full) (Note 14 )
• Lecture 5C (7/21): Variance and Covariance. Slides: (blank) (full) (Note 15 )
• Lecture 5D (7/22): Distributions. Slides: (blank) (full) (Note 16 )
• Lecture 6A (7/26): Continuous Probability. Slides: (blank) (full)
• Lecture 6B (7/27): Continuous Distributions 1. Slides: (blank) (full)
• Lecture 6C (7/28): Continuous Distributions 2. Slides: (blank) (full)
• Lecture 6D (7/29): Joint Distributions. Slides: (blank) (full)
• Lecture 7A (8/2): Concentration Inequalities 1. Slides: (blank) (full)
• Lecture 7B (8/3): Concentration Inequalities 2, Confidence Intervals. Slides: (blank) (full)
• Lecture 7C (8/4): Markov Chains 1. Slides: (blank) (full)
• Lecture 7D (8/5): Markov Chains 2. Slides: (blank) (full)
• Lecture Cancelled (8/9): Review
• Lecture Cancelled (8/10): Review
• Lecture Cancelled (8/11): Review
• Lecture Cancelled (8/12): Final Exam