15-251 Great Theoretical Ideas in Computer Science
Home
Schedule
Calendar
Weekly Planner
Policy
Staff
Piazza
Schedule
Week
Date
Day
Topic
Notes
1
Aug
30
T
Introduction
Lecture slides [
PDF
]
Homework 1
Some notes on games
Aug
31
W
On Proofs
Lecture slides [
PDF
]
Sep
1
R
Combinatorial Games
Lecture slides [
PDF
]
Sep
2
F
Recitation 1
Recitation 1 Solutions
2
Sep
6
T
Deterministic Finite Automata
Lecture slides [
PDF
]
Homework 2
Turing's paper
Sep
8
R
Turing Machines
Lecture slides [
PDF
]
Sep
9
F
Recitation 2
Recitation 2 Solutions
3
Sep
13
T
Cantor's Legacy: Countability and Diagonalization
Lecture slides [
PDF
]
Homework 3
Some notes on uncountability
Sep
15
R
Undecidability
Lecture slides [
PDF
]
Sep
16
F
Recitation 3
Recitation 3 Solutions
4
Sep
20
T
Intro to Complexity 1
Lecture slides [
PDF
]
Homework 4
Gödel's letter to von Neumann
Sep
22
R
Intro to Complexity 2
Lecture slides [
PDF
]
Sep
23
F
Recitation 4
Recitation 4 Solutions
5
Sep
27
T
Graphs 1: The Basics
Lecture slides [
PDF
]
Midterm 1 Practice
Some notes on graphs I
Some notes on graphs II
Sep
29
R
Graphs 2: Graph Algorithms
Lecture slides [
PDF
]
Sep
30
F
Recitation 5
Recitation 5 Solutions
6
Oct
4
T
Graphs 3: Stable Matching
Lecture slides [
PDF
]
Homework 5
Some notes on stable matchings
Oct
6
R
Boolean Circuits
Lecture slides [
PDF
]
Oct
7
F
Recitation 6
Recitation 6 Solutions
7
Oct
11
T
NP and NP-completeness 1
Lecture slides [
PDF
]
Homework 6
Oct
13
R
NP and NP-completeness 2
Lecture slides [
PDF
]
Oct
14
F
Recitation 7
Recitation 7 Solutions
8
Oct
18
T
Approximation Algorithms
Lecture slides [
PDF
]
Homework 7
Oct
20
R
Gödel's Incompleteness Theorems
Lecture slides [
PDF
]
Oct
21
F
Mid-Semester Break
9
Oct
25
T
Probability 1
Lecture slides [
PDF
]
Homework 8
Oct
27
R
Probability 2
Lecture slides [
PDF
]
Oct
28
F
Recitation 9
Recitation 9 Solutions
10
Nov
1
T
Randomized Algorithms
Lecture slides [
PDF
]
Homework 9
Nov
3
R
Markov Chains
Lecture slides [
PDF
]
Nov
4
F
Recitation 10
Recitation 10 Solutions
11
Nov
8
T
Modular Arithmetic
Lecture slides [
PDF
]
Midterm 2 Practice
Nov
10
R
Group Theory
Lecture slides [
PDF
]
Nov
11
F
Recitation 11
Recitation 11 Solutions
12
Nov
15
T
Cryptography
Lecture slides [
PDF
]
Homework 10
Nov
17
R
Fields and Polynomials
Lecture slides [
PDF
]
Nov
18
F
Recitation 12
Recitation 12 Solutions
14
Nov
29
T
Error-Correcting Codes
Lecture slides [
PDF
]
Homework 11
Notes on generating functions
Dec
1
R
Generating Functions
Lecture slides [
PDF
]
Dec
2
F
Recitation 14
Recitation 14 Solutions
15
Dec
6
T
A Computational Lens on Proofs
Lecture slides [
PDF
]
Final exam practice questions
Dec
8
R
Epilogue
Lecture slides [
PDF
] [
PDF
]
Dec
9
F
Recitation 15
Recitation 15 Solutions
Course Notes: Definitions and Proofs
