15-251 Great Theoretical Ideas in Computer Science
Home
Schedule
Calendar
Weekly Planner
Policy
Staff
Piazza
15-252
Schedule
Week
Date
Day
Topic
Notes
1
Jan
17
T
Introduction
Lecture slides [
PDF
]
Homework 1
Induction pitfalls
Jan
18
W
On proofs + How to succeed in 251
Lecture slides [
PDF
]
Jan
19
R
Strings and encodings
Lecture slides [
PDF
]
Jan
20
F
Recitation 1
Recitation 1 Solutions
2
Jan
24
T
DFAs 1
Lecture slides [
PDF
] Condensed version [
PDF
]
Homework 2
Automata Tutor
Jan
26
R
DFAs 2
Lecture slides [
PDF
] Condensed version [
PDF
]
Jan
27
F
Recitation 2
Recitation 2 Solutions
3
Jan
31
T
TMs
Lecture slides [
PDF
]
Homework 3
Turing's paper
TM simulator
A Universal TM
Feb
2
R
Cantor's Legacy: To Infinity and Beyond
Lecture slides [
PDF
]
Feb
3
F
Recitation 3
Recitation 3 Solutions
4
Feb
7
T
Turing's Legacy Continues: Decidability and Undecidability 1
Lecture slides [
PDF
]
Homework 4
Feb
9
R
Turing's Legacy Continues: Decidability and Undecidability 2
Lecture slides [
PDF
]
Feb
10
F
Recitation 4
Recitation 4 Solutions
5
Feb
14
T
Computational Complexity 1
Lecture slides [
PDF
]
Homework 5
Gödel's letter to von Neumann
Feb
16
R
Computational Complexity 2
Lecture slides [
PDF
]
Feb
17
F
Recitation 5
Recitation 5 Solutions
6
Feb
21
T
Graphs 1: The Basics
Lecture slides [
PDF
]
Midterm 1 Practice Problems
Feb
23
R
Graphs 2: Basic Graph Algorithms
Lecture slides [
PDF
]
Feb
24
F
Recitation 6
Recitation 6 Solutions
7
Feb
28
T
Graphs 3: Matchings in Bipartite Graphs
Lecture slides [
PDF
]
Homework 6
Mar
2
R
Graphs 4: Stable Matchings
Lecture slides [
PDF
] Condensed version [
PDF
]
Mar
3
F
Recitation 7
Recitation 7 Solutions
8
Mar
7
T
Boolean Formulas and Circuits
Lecture slides [
PDF
]
Homework 7
Mar
9
R
Gödel's Incompleteness Theorems
Lecture slides [
PDF
]
Mar
10
F
No recitation
9
Mar
21
T
NP and NP-completeness 1
Lecture slides [
PDF
]
Homework 8
Mar
23
R
NP and NP-completeness 2
Lecture slides [
PDF
]
Mar
24
F
Recitation 9
Recitation 9 Solutions
10
Mar
28
T
Cook-Levin Theorem
No slides
Homework 9
Mar
30
R
Approximation Algorithms
Lecture slides [
PDF
]
Mar
31
F
Recitation 10
Recitation 10 Solutions
11
Apr
4
T
Intro to Randomness and Probability 1
Lecture slides [
PDF
]
Homework 10
Apr
6
R
Intro to Randomness and Probability 2
Lecture slides [
PDF
]
Apr
7
F
Recitation 11
Recitation 11 Solutions
12
Apr
11
T
Randomized Algorithms Continued
Lecture slides [
PDF
]
Midterm 2 Practice Problems
Apr
13
R
Interactive Proofs
Lecture slides [
PDF
]
Apr
14
F
Recitation 12
Recitation 12 Solutions
13
Apr
18
T
Communication Complexity
Lecture slides [
PDF
]
Homework 11
Apr
20
R
No Classes: Carnival
Apr
21
F
No Recitation: Carnival
14
Apr
25
T
Modular Arithmetic
Lecture slides [
PDF
]
Homework 12
Apr
27
R
Cryptography
Lecture slides [
PDF
]
Apr
28
F
Recitation 14
Recitation 14 Solutions
15
May
2
T
Quantum Computation
Lecture slides [
PDF
]
Final Exam Practice Problems
May
4
R
Epilogue: Guest Lecturers
May
5
F
Recitation 15
Recitation 15 Solutions
Course Notes: Definitions and Proofs
Exercise Solutions/Hints
