Lecture  Lecture Video  Recitation Video  Assignments 
Readings  Resources 
Lecture 1 
01: Lecture  Introduction and Proofs
(transcript) 
Recitation 1,
Recitation Solution 1 
Problem Set 1 
Readings 

Lecture 2 
02: Lecture  Induction
(transcript) 
Recitation 2,
Recitation Solution 2 
Problem Set 2 
Readings 

Lecture 3 
03: Lecture  Strong Induction
(transcript) 
Recitation 3,
Recitation Solution 3 
Problem Set 3 
Readings 
Proof 
Lecture 4 
04: Number Theory I
(transcript) 
Recitation 4,
Recitation Solution 4 
Problem Set 4 
Readings 

Lecture 5 
05: Number Theory II
(transcript) 
Recitation 5,
Recitation Solution 5 
Problem Set 5 
Readings 

Lecture 6 
06: Lecture  Graph Theory and Coloring
(transcript) 
Recitation 6,
Recitation Solution 6 
Problem Set 6 
Readings 

Lecture 7 
07: Lecture  Matching Problems
(transcript) 
Recitation 7,
Recitation Solution 7 
Problem Set 7 
Readings 
Mating 
Lecture 8 
08: Lecture  Graph Theory II: Minimum Spanning Trees
(transcript) 
Recitation 8,
Recitation Solution 8 
Problem Set 8 
Readings 

Lecture 9 
09: Lecture  Communication Networks
(transcript) 
Recitation 9,
Recitation Solution 9 
Problem Set 9 
Readings 

Lecture 10 
10: Lecture  Graph Theory III
(transcript) 
Recitation 10,
Recitation Solution 10 
Problem Set 10 
Readings 

Lecture 11 
11: Lecture  Relations, Partial Orders, and Scheduling
(transcript) 
Recitation 1,
Recitation Solution 11 
Problem Set 11 
Readings 

Lecture 12 
12: Lecture  Sums
(transcript) 
Recitation 12,
Recitation Solution 12 
Problem Set 12 
Readings 

Lecture 13 
13: Lecture  Sums and Asymptotics
(transcript) 
Recitation 13,
Recitation Solution 13 

Readings 

Lecture 14 
14: Lecture  Divide and Conquer Recurrences
(transcript) 
Recitation 14,
Recitation Solution 14 

Readings 

Midterm 
Practice Midterm →
Practice Solutions
Midterm →
Midterm Solutions


Lecture 15 
15: Lecture  Linear Recurrences
(transcript) 
Recitation 15,
Recitation Solution 15 

Readings 

Lecture 16 
16: Lecture  Counting Rules I
(transcript) 
Recitation 16,
Recitation Solution 16 

Readings 

Lecture 17 
17: Lecture  Counting Rules II
(transcript) 
Recitation 17,
Recitation Solution 17 

Readings 

Lecture 18 
18: Lecture  Probability Introduction
(transcript) 
Recitation 18,
Recitation Solution 18 

Readings 

Lecture 19 
19: Lecture  Conditional Probability
(transcript) 
Recitation 19,
Recitation Solution 19 

Readings 

Lecture 20 
20: Lecture  Independence
(transcript) 
Recitation 20,
Recitation Solution 20 

Readings 

Lecture 21 
21: Lecture  Random Variables
(transcript) 
Recitation 21,
Recitation Solution 21 

Readings 

Lecture 22 
22: Lecture  Expectation I
(transcript) 
Recitation 22,
Recitation Solution 22 

Readings 

Lecture 23 
23: Lecture  Expectation II
(transcript) 
Recitation 23,
Recitation Solution 23 

Readings 

Lecture 24 
24: Lecture  Large Deviations
(transcript) 
Recitation 24,
Recitation Solution 24 

Readings 

Lecture 25 
25: Lecture  Random Walks
(transcript) 
Recitation 25,
Recitation Solution 25 

Readings 


Final Exam 
Practice Final 2004 →
Final 2004 Solution
Practice Final 2006 →
Final 2006 Solution
Practice Final 2008 →
Final 2008 Solution
Final 2010

