15-251 Great Ideas in Theoretical Computer Science

Schedule


Week Date Day Topic Notes
1 Aug
29		 T Introduction
Slides [PDF] 		Homework 1

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

Automata Tutor
Sep
7		 R DFAs 2
Handout slides [PDF]
Sep
8		 F Recitation 2
Solutions
3 Sep
12		 T Turing Machines
Handout slides [PDF] 		Homework 3

Turing's paper

TM simulator

A Universal TM
Sep
14		 R Church-Turing Thesis, Universality, Decidability
Handout slides [PDF]
Sep
15		 F Recitation 3
Solutions
4 Sep
19		 T Cantor's Legacy
Lecture slides [1 per page | 3 per page] 		Homework 4
Sep
21		 R Turing's Legacy: Undecidability
Lecture slides [1 per page | 3 per page]
Sep
22		 F Recitation 4
Solutions
5 Sep
26		 T Time Complexity
Lecture slides [1 per page | 3 per page] 		Homework 5
Sep
28		 R Cake Cutting
Lecture slides [1 per page | 3 per page]
Sep
29		 F Recitation 5
Solutions
6 Oct
3		 T Graphs I: The Basics
Lecture slides [1 per page | 3 per page] 		Midterm 1 Practice Problems
Oct
5		 R Graphs II: Basic Graph Algorithms
Lecture slides [1 per page | 3 per page]
Oct
6		 F Recitation 6
Solutions
7 Oct
10		 T Graphs III: Matchings and Bipartite Graphs
Handout slides [PDF] 		Homework 6
Oct
12		 R Graphs IV: Stable Matchings
Handout slides [PDF]
Oct
13		 F Recitation 7
Solutions
8 Oct
17		 T Boolean Circuits
Slides handout [PDF] 		Homework 7
Oct
19		 R Polynomial Time Reductions
Lecture slides [1 per page | 3 per page]
Oct
20		 F No recitation
9 Oct
24		 T P vs. NP
Lecture slides [1 per page | 3 per page] 		Homework 8
Oct
26		 R NP and NP-completeness Continued
Handout slides [PDF]
Oct
27		 F Recitation 9
Solutions
10 Oct
31		 T Computational Social Choice
Lecture slides [1 per page | 3 per page] 		Homework 9
Nov
2		 R Approximation Algorithms
Lecture slides [1 per page | 3 per page]
Nov
3		 F Recitation 10
Solutions
11 Nov
7		 T Probability I
Lecture slides [1 per page | 3 per page] 		Midterm 2 Practice Problems
Nov
9		 R Probability II
Lecture slides [1 per page | 3 per page]
Nov
10		 F No recitation
12 Nov
14		 T Randomized Algorithms 1
Handout slides [PDF] 		Homework 10
Nov
16		 R Randomized Algorithms 2
Handout slides [PDF]
Nov
17		 F Recitation 12
Solutions
13 Nov
21		 T Game Theory
Lecture slides [1 per page | 3 per page]
Nov
23		 R No Class: Thanksgiving
Nov
24		 F No Recitation: Thanksgiving
14 Nov
28		 T Modular Arithmetic
Handout notes [PDF] Slides [PDF] 		Homework 11

Notes on Modular Arithmetic and Cryptography
Nov
30		 R Cryptography
Handout slides [PDF]
Dec
1		 F Recitation 14
Solutions
15 Dec
5		 T Quantum Computation
Lecture slides [PDF] 		Final Exam Practice Problems
Dec
7		 R Epilogue: Guest Speakers
Dec
8		 F No recitation