Week 
Date 
Day 
Topic 
Notes 
1 
Sep 1 
T 
Introduction
Lecture slides [PDF] 
Course Notes: Def's and Proofs
Homework 1
Solutions

Sep 3 
R 
On Proofs and Pancakes
Lecture slides [PDF] 
Sep 4 
F 
Recitation 1
Solutions 
2 
Sep 8 
T 
Deterministic Finite Automata
Lecture slides [PDF] 
Turing's paper
Homework 2
Solutions

Sep 10 
R 
Turing Machines
Lecture slides [PDF] 
Sep 11 
F 
Recitation 2
Solutions 
3 
Sep 15 
T 
Countable and Uncountable Sets
Lecture slides [PDF] 
Homework 3
Solutions

Sep 17 
R 
Undecidable Languages
Lecture slides [PDF] 
Sep 18 
F 
Recitation 3
Solutions 
4 
Sep 22 
T 
Time Complexity
Lecture slides [PDF] 
Cake cutting survey
Homework 4
Solutions

Sep 24 
R 
Cake Cutting
Lecture slides [PDF] 
Sep 25 
F 
Recitation 4
Solutions 
5 
Sep 29 
T 
Boolean Circuits
Lecture slides [PDF] 
Homework 5
Solutions

Oct 1 
R 
Graphs I: The Basics
Lecture slides [PDF] 
Oct 2 
F 
Recitation 5
Solutions

6 
Oct 6 
T 
Graphs II: Graph Algorithms
Lecture slides [PDF] 
Midterm 1 practice
Midterm 1 solutions

Oct 8 
R 
Graphs III: Stable and Maximum Matchings
Lecture slides [PDF] 
Oct 9 
F 
Recitation 6
Solutions

7 
Oct 13 
T 
PolynomialTime Reductions
Lecture slides [PDF] 
Homework 6
Solutions

Oct 15 
R 
P vs. NP
Lecture slides [PDF]

Oct 16 
F 
Recitation 7
Solutions

8 
Oct 20 
T 
Computational Social Choice
Lecture slides [PDF] 
Computational social choice survey
Homework 7
Solutions

Oct 22 
R 
Approximation Algorithms
Lecture slides [PDF] 
Oct 23 
F 
No recitation
Midsemester break 
9 
Oct 27 
T 
Online Algorithms
Lecture slides [PDF] 
Homework 8
Solutions

Oct 29 
R 
Probability I
Lecture slides [PDF] 
Oct 30 
F 
Recitation 9
Solutions

10 
Nov 3 
T 
Probability II Lecture slides [PDF] 
Homework 9
Solutions

Nov 5 
R 
Randomized Algorithms Lecture slides [PDF] 
Nov 6 
F 
Recitation 10
Solutions

11 
Nov 10 
T 
Computational Arithmetic Lecture slides [PDF] 
Midterm 2 practice
Midterm 2 solutions

Nov 12 
R 
Cryptography Lecture slides [PDF] 
Nov 13 
F 
Recitation 11
Solutions

12 
Nov 17 
T 
Markov Chains Lecture slides [PDF] 
Homework 10
Solutions
Code 
Nov 19 
R 
Communication Complexity Lecture slides [PDF] 
Nov 20 
F 
Recitation 12
Solutions

13 
Nov 24 
T 
Quantum Computation Lecture slides [PDF] 

Nov 26 
R 
No class: Thanksgiving 
Nov 27 
F 
No class: Thanksgiving 
14 
Dec 1 
T 
Game Theory Lecture slides [PDF] 
Homework 11
Solutions 
Dec 3 
R 
Learning Theory Lecture slides [PDF] 
Dec 4 
F 
Recitation 14
Solutions

15 
Dec 8 
T 
Interactive Proofs Lecture slides [PDF] 
Final practice 
Dec 10 
R 
Epilogue 
Dec 11 
F 
No recitation 