15-251 Great Ideas in Theoretical Computer Science
Home
Course Info
Schedule
Calendar
Weekly Planner
Staff
Notes
Piazza
15-252
Fun
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
]
Nov
23
R
No Class: Thanksgiving
Nov
24
F
No Recitation: Thanksgiving
14
Nov
28
T
Modular Arithmetic
Handout notes [
PDF
] Slides [
PDF
]
Homework 11
Notes on Modular Arithmetic and Cryptography
Nov
30
R
Cryptography
Handout slides [
PDF
]
Dec
1
F
Recitation 14
Solutions
15
Dec
5
T
Quantum Computation
Lecture slides [
PDF
]
Final Exam Practice Problems
Dec
7
R
Epilogue: Guest Speakers
Dec
8
F
No recitation