|
|
|
Date
|
Lecture Topic
|
Homework [Due] /
Solutions
|
Reading
|
Jan
22
|
Intro
- Asymptotics, TMs, TIME(f(n)), P (pdf)
|
Homework 1 (.tex) [1/29]
|
1.0-1.3,1.5
|
Jan
24
|
P,
NP, completeness, coNP, EXP, and NEXP (pdf)
|
HW1
Solutions: 1, 2, 3, 4
|
2
|
Jan
29
|
Space
complexity I (pdf)
|
Homework 2 (.tex) [2/5]
|
4.0,4.2,4.3
|
Jan
31
|
Space
complexity II (pdf)
|
HW2
Solutions: 1, 2, 3, 4
|
4.1,4.4
|
Feb
5
|
Diagonalization
(pdf)
|
Homework 3 (.tex) [2/12]
|
1.4,3
|
Feb
7
|
Polynomial
Heirarchy (pdf)
|
HW3
Solutions: 1, 2, 3, 4
|
5
|
Feb 11
|
Take
Home 1 - due start of class Feb. 12.
|
Exam 1
[2/12]
|
|
Feb
12
|
Circuits I (pdf) |
Homework 4 (.tex) [2/19]
|
6.1,6.6,6.7
|
Feb 14
|
Circuits
II (pdf)
|
|
6.2-6.4
|
Feb
19
|
Circuits
III (pdf)
|
Homework 5 (.tex) [2/26]
|
6.5
|
Feb
21
|
Random
I (pdf)
|
|
7.1-7.3
|
Feb.
26
|
Random
II (pdf)
|
Homework 6 (.tex) [3/4]
|
7.4-7.5,7.B
|
Feb
28
|
Random
III (pdf)
|
|
7.6-7.8
|
Mar
4
|
Random
IV (pdf)
|
Homework 7 (.tex) [3/11]
|
7.10,7.A
|
Mar 5
|
Take
Home 2 -due start of class Mar. 6.
|
Exam 2 (.tex) [3/6]
|
|
Mar
6
|
Counting
I (pdf)
|
|
9.1-9.2
|
Mar
11
|
Counting
II (pdf)
|
Homework 8 (.tex) [3/25]
|
9.2-9.3
|
Mar
13
|
Counting
III (pdf)
|
|
9.3
|
Mar
18
|
SPRING BREAK
|
Mar
20
|
Mar
25
|
Interactive
Proofs I (pdf)
|
Homework 9 (.tex) [4/1]
|
8.1-8.3
|
Mar
27
|
Interactive
Proofs II (pdf)
|
|
8.4, 8.A
|
Apr
1
|
Interactive
Proofs III (pdf)
|
Homework 10 (.tex) [4/8]
|
8.5
|
Apr 2
|
Take
Home 3 - due start of class Apr 3.
|
Exam 3 (.tex) [4/3]
|
|
Apr
3
|
Cryptography
I (pdf)
|
|
(none)
|
Apr
8
|
Cryptography
II (pdf)
|
Homework 11 (.tex) [4/15]
|
10.2
|
Apr
10
|
Cryptography
III (pdf)
|
|
10.1,10.3
|
Apr
15
|
Derandomization
I (pdf)
|
Homework
12 (.tex) [4/22]
|
16.1-16.2
|
Apr
17
|
Derandomization
II (pdf)
|
|
16.2
|
Apr
22
|
Derandomization
III (pdf)
|
Homework 13 (.tex) [4/29]
|
16.3
|
Apr 23
|
Take
Home 4 - due start of class Apr 24.
|
Exam 4 (.tex) [4/24]
|
|
Apr
24
|
PCP
and Approximation
I (pdf)
|
|
18.2
|
Apr
29
|
PCP
and Approximation II (pdf)
|
Homework 14 (.tex) [5/6]
|
18.1-18.3
|
May
1
|
PCP
and Approximation III (pdf)
|
|
18.3-18.4
|
May
6
|
PCP
and Approxmation IV (pdf)
|
|
18.5
|
May
8
|
PCP
and Approximation V
|
|
18.5
|
May 14-15
|
Take Home 5 -
out at noon May 14 / due by 12:30 May 15
|
Exam 5 (.tex)
|
Many of the lecture slides for this course are "inspired by" Steven
Rudich's lecture slides from CS 855 at CMU.
|
|
