| Week |
Date |
Day |
Topic |
Notes |
| 1 |
Jan
17 |
T |
Introduction
Lecture slides [PDF]
|
Homework 1
Induction pitfalls
|
Jan
18 |
W |
On proofs + How to succeed in 251
Lecture slides [PDF]
|
Jan
19 |
R |
Strings and encodings
Lecture slides [PDF]
|
Jan
20 |
F |
Recitation 1
Recitation 1 Solutions
|
|
| 2 |
Jan
24 |
T |
DFAs 1
Lecture slides [PDF] Condensed version [PDF]
|
Homework 2
Automata Tutor
|
Jan
26 |
R |
DFAs 2
Lecture slides [PDF] Condensed version [PDF]
|
Jan
27 |
F |
Recitation 2
Recitation 2 Solutions
|
|
| 3 |
Jan
31 |
T |
TMs
Lecture slides [PDF]
|
Homework 3
Turing's paper
TM simulator
A Universal TM
|
Feb
2 |
R |
Cantor's Legacy: To Infinity and Beyond
Lecture slides [PDF]
|
Feb
3 |
F |
Recitation 3
Recitation 3 Solutions
|
|
| 4 |
Feb
7 |
T |
Turing's Legacy Continues: Decidability and Undecidability 1
Lecture slides [PDF]
|
Homework 4
|
Feb
9 |
R |
Turing's Legacy Continues: Decidability and Undecidability 2
Lecture slides [PDF]
|
Feb
10 |
F |
Recitation 4
Recitation 4 Solutions
|
|
| 5 |
Feb
14 |
T |
Computational Complexity 1
Lecture slides [PDF]
|
Homework 5
Gödel's letter to von Neumann
|
Feb
16 |
R |
Computational Complexity 2
Lecture slides [PDF]
|
Feb
17 |
F |
Recitation 5
Recitation 5 Solutions
|
|
| 6 |
Feb
21 |
T |
Graphs 1: The Basics
Lecture slides [PDF]
|
Midterm 1 Practice Problems
|
Feb
23 |
R |
Graphs 2: Basic Graph Algorithms
Lecture slides [PDF]
|
Feb
24 |
F |
Recitation 6
Recitation 6 Solutions
|
|
| 7 |
Feb
28 |
T |
Graphs 3: Matchings in Bipartite Graphs
Lecture slides [PDF]
|
Homework 6
|
Mar
2 |
R |
Graphs 4: Stable Matchings
Lecture slides [PDF] Condensed version [PDF]
|
Mar
3 |
F |
Recitation 7
Recitation 7 Solutions
|
|
| 8 |
Mar
7 |
T |
Boolean Formulas and Circuits
Lecture slides [PDF]
|
Homework 7
|
Mar
9 |
R |
Gödel's Incompleteness Theorems
Lecture slides [PDF]
|
Mar
10 |
F |
No recitation
|
|
| 9 |
Mar
21 |
T |
NP and NP-completeness 1
Lecture slides [PDF]
|
Homework 8
|
Mar
23 |
R |
NP and NP-completeness 2
Lecture slides [PDF]
|
Mar
24 |
F |
Recitation 9
Recitation 9 Solutions
|
|
| 10 |
Mar
28 |
T |
Cook-Levin Theorem
No slides
|
Homework 9
|
Mar
30 |
R |
Approximation Algorithms
Lecture slides [PDF]
|
Mar
31 |
F |
Recitation 10
Recitation 10 Solutions
|
|
| 11 |
Apr
4 |
T |
Intro to Randomness and Probability 1
Lecture slides [PDF]
|
Homework 10
|
Apr
6 |
R |
Intro to Randomness and Probability 2
Lecture slides [PDF]
|
Apr
7 |
F |
Recitation 11
Recitation 11 Solutions
|
|
| 12 |
Apr
11 |
T |
Randomized Algorithms Continued
Lecture slides [PDF]
|
Midterm 2 Practice Problems
|
Apr
13 |
R |
Interactive Proofs
Lecture slides [PDF]
|
Apr
14 |
F |
Recitation 12
Recitation 12 Solutions
|
|
| 13 |
Apr
18 |
T |
Communication Complexity
Lecture slides [PDF]
|
Homework 11
|
Apr
20 |
R |
No Classes: Carnival
|
Apr
21 |
F |
No Recitation: Carnival
|
|
| 14 |
Apr
25 |
T |
Modular Arithmetic
Lecture slides [PDF]
|
Homework 12
|
Apr
27 |
R |
Cryptography
Lecture slides [PDF]
|
Apr
28 |
F |
Recitation 14
Recitation 14 Solutions
|
|
| 15 |
May
2 |
T |
Quantum Computation
Lecture slides [PDF]
|
Final Exam Practice Problems
|
May
4 |
R |
Epilogue: Guest Lecturers
|
May
5 |
F |
Recitation 15
Recitation 15 Solutions
|
|
