15-251 Great Theoretical Ideas in Computer Science
Home
Schedule
Policy
Staff
Piazza
Calendar
Week
Date
Day
Topic
Notes
1
Jan
13
T
Introduction
Lecture slides [
PDF
]
Homework 1
Solutions
Jan
15
R
Deductive Systems and Propositional Logic
Lecture slides [
PDF
]
Jan
16
F
Recitation 01
Solutions
2
Jan
20
T
Formalization of Proof
Lecture slides [
PDF
]
Homework 2
Solutions
Jan
22
R
Finite Automata
Lecture slides [
PDF
]
Jan
23
F
Recitation 02
Solutions
3
Jan
27
T
Turing's Legacy
Lecture slides [
PDF
]
Turing's paper
Homework 3
Solutions
Jan
29
R
Uncountability and Uncomputability
Lecture slides [
PDF
]
Jan
30
F
Recitation 03
Solutions
4
Feb
3
T
Introduction to Computational Complexity I
Lecture slides [
PDF
]
Midterm 1 practice
Gödel's letter to von Neumann
Feb
5
R
Introduction to Computational Complexity II
Lecture slides [
PDF
]
Feb
6
F
Recitation 04
Solutions
5
Feb
10
T
Space Complexity and Circuit Complexity
Lecture slides [
PDF
]
Midterm 1 on Feb 11, 18:30-21:30
Covers weeks 1-3
Midterm 1 Solutions
Homework 4
Solutions
Feb
12
R
Graphs: The Basics
Lecture slides [
PDF
]
Feb
13
F
Recitation 05
Solutions
6
Feb
17
T
Graph Algorithms
Lecture slides [
PDF
]
Homework 5
Solutions
Feb
19
R
Graph Algorithms II: Stable and Maximum Matchings
Lecture slides [
PDF
]
Feb
20
F
Recitation 06
Solutions
7
Feb
24
T
NP and NP-completeness I
Lecture slides [
PDF
]
Homework 6
Solutions
Feb
26
R
NP and NP-completeness II
Lecture notes [
PDF
]
Feb
20
F
Recitation 07
Solutions
8
Mar
3
T
Approximation Algorithms
Lecture slides [
PDF
]
Midterm 2 practice
Mar
5
R
Gödel's Incompleteness Theorems
Lecture slides [
PDF
]
9
Mar
17
T
Probability I
Lecture slides [
PDF
]
Midterm 2 on Mar 18, 18:30-21:30
Covers weeks 4-7
Midterm 2 Solutions
Homework 7
Solutions
Mar
19
R
Probability II
Lecture slides [
PDF
]
Mar
20
F
Recitation 08
Solutions
10
Mar
24
T
Randomized Algorithms
Lecture slides [
PDF
]
Homework 8
Solutions
Mar
26
R
Computational arithmetic
Lecture slides [
PDF
]
Mar
27
F
Recitation 09
Solutions
11
Mar
31
T
Cryptography
Lecture slides [
PDF
]
Homework 9
Solutions
Apr
2
R
Polynomials
Lecture slides [
PDF
]
Mar
27
F
Recitation 10
Solutions
12
Apr
7
T
Linear Algebra
Lecture slides [
PDF
]
Homework 10
Solutions
Apr
9
R
Markov Chains
Lecture slides [
PDF
]
Apr
10
F
Recitation 11
Solutions
13
Apr
14
T
Quantum computation
Lecture slides [
PDF
]
Midterm 3 on Apr 15, 18:30-21:30
Covers weeks 8-11
Midterm 3 Solutions
Apr
16
R
No class: Carnival
Apr
17
F
No Class: Carnival
14
Apr
21
T
Communication Complexity
Lecture slides [
PDF
]
Homework 11
Apr
23
R
A Computational Lens on Proofs
Lecture slides [
PDF
]
Apr
24
F
Recitation 12
15
Apr
28
T
Epilogue I
Lecture slides [
PDF
]
Final Exam on May 8th
5:30-8:30 CUC McConomy
Practice problems
.
Covers everything except Gödel and weeks 13-15.
Apr
30
R
Epilogue II
Lecture slides [
PDF
]
May
1
F
Various topics: Game theory, infinity, exam review, group theory and
TA feedback
