15-251 Great Theoretical Ideas in Computer Science
Home
Schedule
Calendar
Weekly Planner
Policy
Staff
Piazza
Schedule
Week
Date
Day
Topic
Notes
1
Sep
1
T
Introduction
Lecture slides [
PDF
]
Course Notes:
Def's and Proofs
Homework 1
Solutions
Sep
3
R
On Proofs and Pancakes
Lecture slides [
PDF
]
Sep
4
F
Recitation 1
Solutions
2
Sep
8
T
Deterministic Finite Automata
Lecture slides [
PDF
]
Turing's paper
Homework 2
Solutions
Sep
10
R
Turing Machines
Lecture slides [
PDF
]
Sep
11
F
Recitation 2
Solutions
3
Sep
15
T
Countable and Uncountable Sets
Lecture slides [
PDF
]
Homework 3
Solutions
Sep
17
R
Undecidable Languages
Lecture slides [
PDF
]
Sep
18
F
Recitation 3
Solutions
4
Sep
22
T
Time Complexity
Lecture slides [
PDF
]
Cake cutting survey
Homework 4
Solutions
Sep
24
R
Cake Cutting
Lecture slides [
PDF
]
Sep
25
F
Recitation 4
Solutions
5
Sep
29
T
Boolean Circuits
Lecture slides [
PDF
]
Homework 5
Solutions
Oct
1
R
Graphs I: The Basics
Lecture slides [
PDF
]
Oct
2
F
Recitation 5
Solutions
6
Oct
6
T
Graphs II: Graph Algorithms
Lecture slides [
PDF
]
Midterm 1 practice
Midterm 1 solutions
Oct
8
R
Graphs III: Stable and Maximum Matchings
Lecture slides [
PDF
]
Oct
9
F
Recitation 6
Solutions
7
Oct
13
T
Polynomial-Time Reductions
Lecture slides [
PDF
]
Homework 6
Solutions
Oct
15
R
P vs. NP
Lecture slides [
PDF
]
Oct
16
F
Recitation 7
Solutions
8
Oct
20
T
Computational Social Choice
Lecture slides [
PDF
]
Computational social choice survey
Homework 7
Solutions
Oct
22
R
Approximation Algorithms
Lecture slides [
PDF
]
Oct
23
F
No recitation
Mid-semester break
9
Oct
27
T
Online Algorithms
Lecture slides [
PDF
]
Homework 8
Solutions
Oct
29
R
Probability I
Lecture slides [
PDF
]
Oct
30
F
Recitation 9
Solutions
10
Nov
3
T
Probability II
Lecture slides [
PDF
]
Homework 9
Solutions
Nov
5
R
Randomized Algorithms
Lecture slides [
PDF
]
Nov
6
F
Recitation 10
Solutions
11
Nov
10
T
Computational Arithmetic
Lecture slides [
PDF
]
Midterm 2 practice
Midterm 2 solutions
Nov
12
R
Cryptography
Lecture slides [
PDF
]
Nov
13
F
Recitation 11
Solutions
12
Nov
17
T
Markov Chains
Lecture slides [
PDF
]
Homework 10
Solutions
Code
Nov
19
R
Communication Complexity
Lecture slides [
PDF
]
Nov
20
F
Recitation 12
Solutions
13
Nov
24
T
Quantum Computation
Lecture slides [
PDF
]
Nov
26
R
No class: Thanksgiving
Nov
27
F
No class: Thanksgiving
14
Dec
1
T
Game Theory
Lecture slides [
PDF
]
Homework 11
Solutions
Dec
3
R
Learning Theory
Lecture slides [
PDF
]
Dec
4
F
Recitation 14
Solutions
15
Dec
8
T
Interactive Proofs
Lecture slides [
PDF
]
Final practice
Dec
10
R
Epilogue
Dec
11
F
No recitation
