Links Announcements Homework
Notes Solutions Grades

Com S 531
Theory of Computation
Spring 2006
B029 Atanasoff, MWF 11 -12


 

Instructor:   Pavan Aduri
Office: 102 Atanasoff Hall
Email: pavan AT cs.iastate.edu
Office Hours: M: 10 - 11, F: 1 - 2.
 
 
 
 
 
 
 

 
Teaching Assistant: Xiaoyang Gu
Email:cs511ta@gmail.com
Office:
Office Hours: 4pm Tuesday and Thursday Atanasoff Hall B07

 
 
 
 
 
 
 
 
 
 
 
 
 

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 on Feb 24 (Tentative): 15%
  • Mid Term Exam 2 on April 7 : 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''.