15-251 Great Ideas in Theoretical Computer Science

Schedule


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

Proof checklist

Induction pitfalls

Homework 1
Aug
29		 W On proofs + How to succeed in 251
Slides [PDF]
Aug
30		 R Strings and encodings
Handout slides [PDF]
Aug
31		 F Recitation 1
Solutions
2 Sep
4		 T DFAs 1
Handout slides [PDF] 		Homework 2

Automata Tutor
Sep
6		 R DFAs 2
Handout slides [PDF]
Sep
7		 F Recitation 2
Solutions
3 Sep
11		 T Turing Machines
Lecture slides [1 per page | 3 per page] 		Midterm 1 practice problems

Turing's paper

TM simulator

A Universal TM
Sep
13		 R Church-Turing Thesis, Universality, Decidability
Lecture slides [1 per page | 3 per page]
Sep
14		 F Recitation 3
Solutions
4 Sep
18		 T Midterm 1 Homework 3
Sep
20		 R Turing's Legacy Continues: Undecidability
Lecture slides [1 per page | 3 per page]
Sep
21		 F Recitation 4
Solutions
5 Sep
25		 T Time Complexity 1
Lecture slides [1 per page | 3 per page] 		Homework 4
Sep
27		 R Time Complexity 2
Lecture slides [1 per page | 3 per page]
Sep
28		 F Recitation 5
Solutions
6 Oct
2		 T Graphs I: The Basics
Lecture slides [1 per page | 3 per page] 		Midterm 2 Practice Problems
Oct
4		 R Graphs II: Basic Graph Algorithms
Lecture slides [1 per page | 3 per page]
Oct
5		 F Recitation 6
Solutions
7 Oct
9		 T Graphs III: Matchings and Bipartite Graphs
Handout slides [PDF] 		Homework 5
Oct
11		 R Graphs IV: Stable Matchings
Handout slides [PDF]
Oct
12		 F Recitation 7
Solutions
8 Oct
16		 T Boolean Circuits
Lecture slides [1 per page | 3 per page] 		Homework 6
Oct
18		 R NP and NP-completeness 1
Handout slides [PDF]
Oct
19		 F Recitation 8
Solutions
9 Oct
23		 T NP and NP-completeness 2
Handout slides [PDF] 		Homework 7
Oct
25		 R Approximation Algorithms
Lecture slides [1 per page | 3 per page]
Oct
26		 F Recitation 9
Solutions
10 Oct
30		 T Introduction to Randomness and Probability Theory Review
Handout slides [PDF] 		Midterm 3 Practice Problems
Nov
1		 R Randomized Algorithms 1
Handout slides [PDF]
Nov
2		 F Recitation 10
Solutions
11 Nov
6		 T Randomized Algorithms 2
Handout slides [PDF] 		Homework 8
Nov
8		 R Modular Arithmetic
Handout notes [PDF]
Nov
9		 F Recitation 11
Solutions
12 Nov
13		 T Group Theory
Lecture slides [1 per page | 3 per page] 		Homework 9
Nov
15		 R Fields and Polynomials
Lecture slides [1 per page | 3 per page]
Nov
16		 F Recitation 12
Solutions
13 Nov
20		 T Quantum Computation
Handout slides [PDF]
Nov
22		 R No Class: Thanksgiving
Nov
23		 F No Recitation: Thanksgiving
14 Nov
27		 T Cryptography
Lecture slides [1 per page | 3 per page] 		Homework 10
Nov
29		 R Interactive Proofs
Lecture slides [1 per page | 3 per page]
Nov
30		 F Recitation 14
Solutions
15 Dec
4		 T Gödel's Incompleteness Theorems
Lecture slides [1 per page | 3 per page] 		Final Exam Practice Problems
Dec
6		 R Epilogue: Guest Speakers
Dec
7		 F No recitation