15-251 Great Ideas in Theoretical Computer Science

Schedule


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 Church-Turing 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
Feb
21
R Boolean circuits
Feb
22
F Recitation 6