15-251 Great Ideas in Theoretical Computer Science

Schedule


Week Date Day Topic Notes
1 Jan
16		 T Introduction
Slides [PDF] 		How to succeed in 251

Proof checklist

Induction pitfalls

Homework 1
Jan
17		 W On proofs + How to succeed in 251
Slides [PDF]
Jan
18		 R Strings and encodings
Handout slides [PDF]
Jan
19		 F Recitation 1
Solutions
2 Jan
23		 T DFAs 1
Handout slides [PDF] 		Homework 2

Automata Tutor
Jan
25		 R DFAs 2
Handout slides [PDF]
Jan
26		 F Recitation 2
Solutions
3 Jan
30		 T Turing Machines
Handout slides [PDF] 		Homework 3

Turing's paper

TM simulator

A Universal TM
Feb
1		 R Church-Turing Thesis, Universality, Decidability
Handout slides [PDF]
Feb
2		 F Recitation 3
Solutions
4 Feb
6		 T Cantor's Legacy
Lecture slides [1 per page | 3 per page] 		Homework 4
Feb
8		 R Turing's Legacy: Undecidability
Lecture slides [1 per page | 3 per page]
Feb
9		 F Recitation 4
Solutions
5 Feb
13		 T Time Complexity
Lecture slides [1 per page | 3 per page] 		Homework 5

Gödel's letter to von Neumann
Feb
15		 R More Complexity
Lecture slides [1 per page | 3 per page]
Feb
16		 F Recitation 5
Solutions
6 Feb
20		 T Stable Matchings
Handout slides [PDF] 		Midterm 1 Practice Problems
Feb
22		 R Graphs I: The Basics
Handout slides [PDF]
Feb
23		 F Recitation 6
Solutions
7 Feb
27		 T Graphs II: Representation and Exploration
Lecture slides [1 per page | 3 per page] 		Homework 6
Mar
1		 R Graphs III: Spanning Trees and Matchings
Lecture slides [1 per page | 3 per page]
Mar
2		 F Recitation 7
Solutions
8 Mar
6		 T Boolean Circuits
Handout slides [PDF] 		Homework 7
Mar
8		 R NP and NP-completeness 1
Handout slides [PDF]
Mar
9		 F No recitation
9 Mar
20		 T Cook-Levin
Lecture slides [1 per page | 3 per page] 		Homework 8
Mar
22		 R NP and NP-completeness Continued
Handout slides [PDF]
Mar
23		 F Recitation 9
Solutions
10 Mar
27		 T Approximation Algorithms
Lecture slides [1 per page | 3 per page] 		Homework 9
Mar
29		 R Probability Review
Lecture slides [1 per page | 3 per page]
Mar
30		 F Recitation 10
Solutions
11 Apr
3		 T Randomized Algorithms I
Handout slides [PDF] 		Homework 10
Apr
5		 R Randomized Algorithms II
Handout slides [PDF]
Apr
6		 F Recitation 11
Solutions
12 Apr
10		 T NP and Logic
Lecture slides [1 per page | 3 per page] 		Midterm 2 Practice Problems
Apr
12		 R Transducers
Lecture slides [1 per page | 3 per page]
Apr
13		 F No recitation
13 Apr
17		 T Presburger Arithmetic
Lecture slides [1 per page | 3 per page] 		Homework 11
Apr
19		 R No Class: Carnival
Apr
20		 F No Recitation: Carnival
14 Apr
24		 T Modular Arithmetic
Handout notes [PDF] 		Homework 12

Notes on Modular Arithmetic and Cryptography
Apr
26		 R Cryptography
Handout slides [PDF]
Apr
27		 F Recitation 14
Solutions
15 May
1		 T Quantum Computation
Lecture slides [PDF] 		Final Exam Practice Problems
May
3		 R Epilogue: Guest Speakers
May
4		 F No recitation