Automata2_Spring14

Objectives:

This is the first course in theoretical computer science. As opposed to other courses in computer science, the purpose of this course is to ask very fundamental questions about computations. The main questions addressed in this course are:

• What is a computation?
• Is there a universal model of computation?
• Can every problem be computed?
• Can we identify problems that are not computable?
• How much resources are needed to solve a problem?
• Can we classify problems that can be solved in principle (given a lot of resources) but cannot be solved in practice?

The theme of the course is to pose these problems in a mathematically precise way. Furthermore, we will answer these questions in a rigorous fashion.

Text Book:

• Michael Sipser, Introduction to the Theory of Computation (2^nd Edition, Thomson Publishing, 2006)

Note: Part I of the book (chapters 0, 1 and 2) are covered in previous courses. We may briefly visit them if there is a need for it. However, major part of this course would be from Part II and III of this book.

• John Martin, Introduction to Languages and the Theory of Computation (3^rd Edition, McGraw-Hill, 2002)

Reference Book:

• Christos H. Papadimitriou, Computational Complexity (Addison Wesley, 1994)

• John E. Hopcroft, Introduction to Automata Theory, Languages, and Computation, ( Addison-Wesley, 1979, ISBN 0-201-02988)

Syllabus and Schedule: