Com S 531
Theory of Computation
Spring 2013
Carver 0204, MWF 11 -11:50

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

 
Teaching Assistant: Adam Case
Email: adamcase@ AT iastate.edu
Office: Pearson 0145
Office Hours: T 9:30-10:30, R 1-2
 
 
 
 
 
 
 
 
 
 
 

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: 45%

• Mid Term Exam : 20%

• Final Exam: 35%

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