Teaching Assistant: Aaron Sterling
Email:sterling AT cs.iastate.edu
Office: Pearson 0145
Office Hours: T 11-12, R 2:30-3:30
 
 
 
 
 

 
Teaching Assistant: Xiaoyang Gu
Email:cs511ta_AT_gmail.com
Office: Atanasoff B07
Office Hours: T 4-5, R 11-12
 
 
 
 

Textbook: Computability and Complexity Theory. S. Homer and A. Selman, Springer Verlag, 2001. We will cover most of the text. Occasionally, I may teach the material that does not appear in the text.
Web Page:  http://www.cs.iastate.edu/~cs531. Check the class homepage regularly for news, home works, solutions etc.

Grades:

Home Works: 40%

Mid Term Exam 1 : 15%

Mid Term Exam 2 : 15%

Final Exam: 30%

The goal of Theory of computation is to identify the fundamental laws obeyed by the computer on your desk. This course addresses following questions.

Computability theory. What is a computer? What is an algorithm/program? What problems can computer solve? Are there problems for which no programs exist?

 Complexity theory. What problems can be solved efficiently? Are there problems for which no efficient programs exist? Can we classify problems based on the amount of resources needed to solve them?

This is one the fields that makes ''Computer Science'' a ''Science''.