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]
Homework 11
Nov
23
R No Class: Thanksgiving
Nov
24
F No Recitation: Thanksgiving