| Unit 1: Proofs |
| 1 |
1.1 Intro to Proofs |
Chapter 1.1–1.6 (PDF) |
Welcome to 6.042J (PDF)
Introduction to Proofs (PDF)
|
Session 1 In-Class Questions (PDF) |
Problem Set 1 (PDF) |
| 2 |
1.2 Proof Methods |
Chapter 1.7–1.9 (PDF) |
Proof by Contradiction (PDF)
Proof by Cases (PDF)
Proof by Cases Example (PDF)
|
Session 2 In-Class Questions (PDF) |
| 3 |
1.3 Well Ordering Principle |
Chapter 2.1–2.3 (PDF) |
Well Ordering Principle 1 (PDF)
Well Ordering Principle 2 (PDF)
Well Ordering Principle 3 (PDF)
|
Session 3 In-Class Questions (PDF) |
| 4 |
1.4 Logic & Propositions |
Chapter 3.1–3.5 (PDF) |
Propositional Operators (PDF)
Digital Logic (PDF)
Truth Tables (PDF)
Implies (PDF)
Propositional Logic (PDF)
|
Session 4 In-Class Questions (PDF) |
| 5 |
1.5 Quantifiers & Predicate Logic |
Chapter 3.6 (PDF) |
Predicate Logic 1 (PDF)
Predicate Logic 2 (PDF)
Predicate Logic 3 (PDF)
|
Session 5 In-Class Questions (PDF) |
Problem Set 2 (PDF) |
| 6 |
1.6 Sets |
Chapter 4.1–4.2 (PDF) |
Sets Definition (PDF)
Sets Operation (PDF)
|
Session 6 In-Class Questions (PDF) |
| 7 |
1.7 Binary Relations |
Chapter 4.3–4.5 (PDF) |
Relations (PDF)
Relational Mapping (PDF)
Finite Cardinality (PDF)
|
Session 7 In-Class Questions (PDF) |
Problem Set 3 (PDF) |
| 8 |
1.8 Induction |
Chapter 5.1–5.3 (PDF) |
Induction (PDF)
Bogus Induction (PDF - 1.2MB)
Strong Induction (PDF)
Ordinary Induction vs Strong Induction vs WOP (PDF)
|
Session 8 In-Class Questions (PDF) |
| 9 |
1.9 State Machines—Invariants |
Chapter 5.4 (PDF) |
State Machine Invariants (PDF)
Derived Variables (PDF)
|
Session 9 In-Class Questions (PDF) |
Problem Set 4 (PDF) |
| 10 |
1.10 Recursive Definition |
Chapter 6 (PDF) |
Recursive Data (PDF)
Structural Induction (PDF)
Recursive Functions (PDF)
|
Session 10 In-Class Questions (PDF) |
| 11 |
1.11 Infinite Sets |
Chapter 7 (PDF) |
Cardinality (PDF)
Countable Sets (PDF)
Cantor's Theorem (PDF)
The Halting Problem (PDF)
Russell's Paradox (PDF)
Set Theory Axioms (PDF)
|
Session 11 In-Class Questions (PDF) |
| Unit 2: Structures |
| 12 |
2.1 GCDs |
Chapter 8.1–8.5 (PDF) |
GCDs and Linear Combinations (PDF)
Euclidean Algorithm (PDF)
The Pulverizer (PDF)
Die Hard Primes (PDF)
Prime Factorization (PDF)
|
Session 12 In-Class Questions (PDF) |
Problem Set 5 (PDF) |
| 13 |
2.2 Congruences |
Chapter 8.6–8.9 (PDF) |
Congruence (PDF)
Inverses Mod N (PDF)
|
Session 13 In-Class Questions (PDF) |
| 14 |
2.3 Euler's Theorem |
Chapter 8.10 (PDF) |
Modular Exponentiation: Euler's Function (PDF)
The Ring Z_n (PDF)
|
Session 14 In-Class Questions (PDF) |
| 15 |
2.4 RSA Encryption |
Chapter 8.11–8.12 (PDF) |
RSA Public Key Encryption (PDF)
Reducing Factoring to SAT (PDF)
|
Session 15 In-Class Questions (PDF) |
Problem Set 6 (PDF) |
| 16 |
2.5 Digraphs: Walks & Paths |
Chapter 9.1–9.4 (PDF) |
Digraphs: Walks & Paths (PDF)
Digraphs: Connected Vertices (PDF)
|
Session 16 In-Class Questions (PDF) |
| 17 |
2.6 Directed Acyclic Graphs |
Chapter 9.5 (PDF) |
DAGs (PDF)
Scheduling (PDF)
Time vs Processors (PDF)
|
Session 17 In-Class Questions (PDF) |
Problem Set 7 (PDF) |
| 18 |
2.7 Partial Orders and Equivalence |
Chapter 9.5–9.11 (PDF) |
Partial Orders (PDF)
Representing Partial Orders As Subset Relations (PDF)
Equivalence Relations (PDF)
|
Session 18 In-Class Questions (PDF) |
| 19 |
2.8 Degrees & Isomorphism |
Chapter 11.1–11.4 (PDF) |
Degrees (PDF)
Isomorphism (PDF)
|
Session 19 In-Class Questions (PDF) |
| 20 |
2.9 Coloring & Connectivity |
Chapter 11.7–11.9 (PDF) |
Coloring (PDF)
Connectivity (PDF)
k-Connectivity (PDF)
|
Session 20 In-Class Questions (PDF) |
Problem Set 8 (PDF) |
| 21 |
2.10 Trees |
Chapter 11.9–11.10 (PDF) |
Trees (PDF)
Tree Coloring (PDF)
Spanning Trees (PDF)
|
Session 21 In-Class Questions (PDF) |
| 22 |
2.11 Stable Matching |
Chapter 11.6 (PDF) |
Stable Matching (PDF - 2.6MB)
Mating Ritual (PDF)
Optimal Stable Matching (PDF)
Bipartite Matching (PDF)
Hall's Theorem (PDF)
|
Session 22 In-Class Questions (PDF) |
|
Unit 3: Counting |
| 23 |
3.1 Sums & Products |
Chapter 13.1–13.5 (PDF) |
Arithmetic Sums (PDF)
Geometric Sums (PDF)
Book Stacking (PDF)
Integral Method (PDF)
Stirling's Formula (PDF)
|
Session 23 In-Class Questions (PDF) |
Problem Set 9 (PDF) |
| 24 |
3.2 Asymptotics |
Chapter 13.7 (PDF) |
Asymptotic Notation (PDF)
Asymptotic Properties (PDF)
Asymptotic Blunders (PDF)
|
Session 24 In-Class Questions (PDF) |
| 25 |
3.3 Counting with Bijections |
Chapter 14.1–14.2 (PDF) |
Sum and Product Rules (PDF)
Counting with Bijections (PDF)
|
Session 25 In-Class Questions (PDF) |
Problem Set 10 (PDF) |
| 26 |
3.4 Repetitions & Binomial Theorem |
Chapter 14.4–14.7 (PDF) |
Generalized Counting Rules (PDF)
Two Pair Poker Hands (PDF)
Binomial Theorem (PDF)
Bookkeeper Rule, Multinomial Theorem (PDF)
|
Session 26 In-Class Questions (PDF) |
| 27 |
3.5 Pigeonhole Principle, Inclusion-Exclusion |
Chapter 14.8 (PDF) |
The Pigeonhole Principle (PDF)
Inclusion-Exclusion (PDF)
Inclusion-Exclusion: 2 Set Proof (PDF)
|
Session 27 In-Class Questions (PDF) |
|
Unit 4: Probability |
| 28 |
4.1 Intro to Discrete Probability |
Chapter 16.1–16.5 (PDF) |
Tree Model (PDF)
Simplified Monty Hall Tree (PDF)
Sample Spaces (PDF)
|
Session 28 In-Class Questions (PDF) |
Problem Set 11 (PDF) |
| 29 |
4.2 Conditional Probability |
Chapter 17.1–17.5 (PDF) |
Conditional Probability (PDF)
Law Of Total Probability (PDF)
Bayes' Theorem (PDF)
Monty Hall Problem (PDF)
|
Session 29 In-Class Questions (PDF) |
| 30 |
4.3 Independence & Causality |
Chapter 17.7–17.8 (PDF) |
Independence (PDF)
Mutual Independence (PDF)
|
Session 30 In-Class Questions (PDF) |
Problem Set 12 (PDF) |
| 31 |
4.4 Random Variables, Density Functions |
Chapter 18.1–18.3 (PDF) |
Bigger Number Game (PDF)
Random Variables: Independence (PDF)
Random Variables: Uniform & Binomial (PDF)
|
Session 31 In-Class Questions (PDF) |
| 32 |
4.5 Expectation |
Chapter 18.4–18.5 (PDF) |
Expectation (PDF)
Expected Number Of Heads (PDF)
Total Expectation (PDF)
Mean Time To Failure (PDF)
Linearity Of Expectation (PDF)
|
Session 32 In-Class Questions (PDF) |
| 33 |
4.6 Deviation: Markov & Chebyshev Bounds |
Chapter 19.1–19.3 (PDF) |
Deviation From The Mean (PDF)
Markov Bounds (PDF)
Chebyshev Bounds (PDF)
Variance (PDF)
|
Session 33 In-Class Questions (PDF) |
No Assignment |
| 34 |
4.7 Sampling & Confidence |
Chapter 19.4–19.5 (PDF) |
Law of Large Numbers (PDF)
Independent Sampling Theorem (PDF)
Birthday Matching (PDF)
Sampling and Confidence (PDF)
|
Session 34 In-Class Questions (PDF) |
| 35 |
4.8 Random Walks & Pagerank |
Chapter 20.2 (PDF) |
Random Walks (PDF)
Stationary Distributions (PDF)
Pagerank (PDF)
|
Session 35 In-Class Questions (PDF) |
