Week 
Date 
Day 
Topic 
Notes 
1 
Jan 15 
T 
Introduction
Slides [PDF]

How to succeed in 251
Proof checklist
Induction pitfalls
Homework 1

Jan 16 
W 
On proofs + How to succeed in 251
Slides [PDF]

Jan 17 
R 
Strings and encodings, Decision Problems, Induction Review, Finite Automata preview
Slides [PDF]

Aug 31 
F 
Recitation 1
Solutions

2 
Jan 22 
T 
Finite Automata
Handout slides [PDF]

Homework 2
Automata Tutor

Jan 24 
R 
Turing Machines
Handout slides [PDF]

Jan 25 
F 
Recitation 2
Solutions

3 
Jan 29 
T 
ChurchTuring Thesis, Universality, Decidability
Handout slides [PDF]

Turing's paper
TM simulator
A Universal TM
Homework 3

Jan 31 
R 
Class canceled due to weather :(

Feb 1 
F 
Recitation 3
Solutions

4 
Feb 5 
T 
Undecidability, Reductions; Time Complexity I
Handout slides [PDF]

Homework 4

Feb 7 
R 
Time Complexity II
Handout slides [PDF]

Feb 8 
F 
Recitation 4
Solutions

5 
Feb 12 
T 
Graphs I: Basics
Handout slides [PDF]

Midterm 1 Practice

Feb 14 
R 
Graphs II: DFS, MST, Matchings
Handout slides [PDF] 
Feb 15 
F 
Recitation 5
Solutions

6 
Feb 19 
T 
Graphs III, Stable Matchings

Homework 5

Feb 21 
R 
Boolean Circuits

Feb 22 
F 
Recitation 6
Solutions

7 
Feb 26 
T 
Efficient Reductions
Handout slides [PDF]

Homework 6

Feb 28 
R 
P vs. NP, and NPcompleteness
Handout slides [PDF]

Mar 1 
F 
Recitation 7
Solutions

8 
Mar 5 
T 
Approximation Algorithms
Handout slides [PDF]

Homework 7
Partial notes on games

Mar 7 
R 
Combinatorial Games
Handout slides [PDF]

Mar 8 
F 
no recitation (midsemester break)

9 
Mar 1115 
MF 
Spring Break

10 
Mar 19 
T 
Introduction to Probability
Handout slides [PDF]

Homework 8

Mar 22 
R 
Randomized Algorithms I
Handout slides [PDF]

Mar 23 
F 
Recitation 8
Solutions

11 
Mar 26 
T 
Randomized Algorithms II
Handout slides [PDF]

Homework 9

Mar 28 
R 
Communication Complexity
Handout slides [PDF]

Mar 29 
F 
Recitation 9
Solutions

12 
Apr 2 
T 
Modular Arithmetic
Handout slides [PDF]

Midterm 2 Review

Apr 4 
R 
Group Theory
Handout slides [PDF]

Apr 5 
F 
Recitation 10
Solutions

13 
Apr 9 
T 
Fields and Polynomials
Slides [PDF]

No Homework

Apr 10 
W 
Midterm 2

Apr 11 
R 
no lecture (carnival)

Apr 12 
F 
no recitation (carnival)

14 
Apr 16 
T 
Error Correcting Codes
Slides [PDF]

Homework 10

Apr 18 
R 
Theoretical CS redefines proofs: Interactive, ZeroKnowledge, SpotCheckable
Slides [PDF]

Apr 19 
F 
Recitation 11
Solutions

15 
Apr 23 
T 
Cryptography I
Slides [PDF]

Homework 11

Apr 25 
R 
Cryptography II
Slides [PDF]

Apr 26 
F 
Recitation 12
Solutions

16 
Apr 30 
T 
Godel Incompleteness Theorems
Slides [PDF]

Godel incompleteness & surprise exam paradox
Fall 2018 Final
Final Review Problems
Study Guide

May 2 
R 
Epilogue
[Slides] [15295 Competitive programming]

May 3 
F 
Recitation 13

17 
May 6 
M 
Final Exam
