Office hours: Wed 530620pm, CSE 640
Office hours: TBD
Class email list: csep531a_sp16 [click link to sign up]
[archives]
Discussion board
date  topic  slides  reading  
30Mar  Cardinality of sets Turing machines, decidability 
Sipser  3.13.3, 4.14.2  
13Apr  Universal Turing machines [epic Game of Life video] Undecidability of the halting problem Reductions Time complexity and polynomial time 
Sipser  5.15.3; 7.17.2  
20Apr 
Nondeterministic Turing machines and NP Polynomialtime reductions and NPcompleteness 
Sipser AroraBarak 
7.17.4 1.5, 2.12.3 

27Apr  More NPcompleteness reductions

Sipser AroraBarak 
7.47.5 2.22.4 

4May  Space complexity

Sipser AroraBarak 
8.18.4, 9.1 4.14.3 

11May  Interactive proofs and IP=PSPACE

AroraBarak  8.18.5  
18May  Logarithmic space computation
 Sipser  8.48.6  
25May  Randomness and computation

ppt 
supplementary  
1Jun 