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