Class InfoClass Number: APPM 814Dates: Mar 6, 2012  Jun 7, 2012 Room: NS 319 Meeting time:
Purpose: Introduction to Mathematical Complexity Theory and Computation Text: Peter Gacs and Laszlo Lovasz, Computation Complexity, Lecture Notes 

Week  Topics  Chapters 
1  The Turing Machine  1 & 2 
2  RAM and Logic Circuits  2 
3  Decidability  2 & 3 
4  Undecidable Problems  3 
5  Complexity Classes  4 
6  Space and Time  4 
7  NonDeterministic Computation  5 
8  Midterm Exam  
9  NPCompleteness  5 
10  Randomization  6 
11  Information Complexity  7 
12  Kolmogorov Complexity  7 
13  Parallel Computing  8 
14  Decision Trees  9 
15  Final Exam 
Attendance  10% 
Midterm:  40% 
Final:  50% 