Skip to main content

LECTURESREADINGSLECTURE SLIDESIN-CLASS QUESTIONSASSIGNMENTS
Unit 1: Proofs
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)
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)
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)
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)
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)
1.6 Sets Chapter 4.1–4.2 (PDF)

Sets Definition (PDF)

Sets Operation (PDF)

Session 6 In-Class Questions (PDF)
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)
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)
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)
1.10 Recursive Definition Chapter 6 (PDF)

Recursive Data (PDF)

Structural Induction (PDF)

Recursive Functions (PDF)

Session 10 In-Class Questions (PDF)
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
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)
2.2 Congruences Chapter 8.6–8.9 (PDF)

Congruence (PDF)

Inverses Mod N (PDF)

Session 13 In-Class Questions (PDF)
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)
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)
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)
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)
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)
2.8 Degrees & Isomorphism Chapter 11.1–11.4 (PDF)

Degrees (PDF)

Isomorphism (PDF)

Session 19 In-Class Questions (PDF)
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)
2.10 Trees Chapter 11.9–11.10 (PDF)

Trees (PDF)

Tree Coloring (PDF)

Spanning Trees (PDF)

Session 21 In-Class Questions (PDF)
2.11 Stable Matching Chapter 11.6 (PDF)

Stable Matching (PDF)

Mating Ritual (PDF)

Optimal Stable Matching (PDF)

Bipartite Matching (PDF)

Hall's Theorem (PDF)

Session 22 In-Class Questions (PDF)
Unit 3: Counting  
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)
3.2 Asymptotics Chapter 13.7 (PDF)

Asymptotic Notation (PDF)

Asymptotic Properties (PDF)

Asymptotic Blunders (PDF)

Session 24 In-Class Questions (PDF)
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)
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)
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  
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)
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)
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)
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)
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)
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
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)
4.8 Random Walks & Pagerank Chapter 20.2 (PDF)

Random Walks (PDF)

Stationary Distributions (PDF)

Pagerank (PDF)

Session 35 In-Class Questions (PDF)