automata2_spring15

Credit Hours: 3

Pre-Requisites: Theory of Automata, Discrete Mathematics

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:

• Marks of Final

Evaluation Criteria (Tentative):

Assignments 10 % (+5%)

Quizzes 10 % (+5%)

Term Paper (10 %)

Midterm 30 %

Final 40 %

Policy:

• Cheating will lead to zero weightage in all assignments/quizzes/both or more.
• There will be many quizzes and assignments, but only 3 random of each will be marked.