Com S 531
Theory of Computation
Spring 2009
Gillman 1104, MWF 11 -11:50

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

 
Teaching Assistant: Aaron Sterling
Email: sterling@cs.iastate.edu
Office: Pearson 145
Office Hours: Thursdays 2pm-4pm
 
 
 
 
 
 
 
 
 
 
 

Textbook: There is no required textbook. I will provide some notes. However, I will not provide notes for all the topics discussed in class. You are expected to take notes during the lectures. There are quite a few reference books. Below is a partial list:

• Computability and Complexity Theory. Homer and Selman.

• Automata, Languages and Computing. Hopcroft, Motwani, and Ullman

• Elements of Theory of Computation. Papadimitriou.

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''.