15-251 Great Theoretical Ideas in Computer Science

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


Valid CSS! Valid XHTML 1.0 Strict