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
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 NP-completeness
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
11-15
M-F 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, Zero-Knowledge, Spot-Checkable
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] [15-295 Competitive programming]
May
3
F Recitation 13
17 May
6
M Final Exam