Class timings

Slot: C
Hours: M 9:30-10:25, W 7:30-9:25, Th 9:30-10:25
Room No: CSE 119

Syllabus

Mathematical preliminaries	Sets, functions and relations, strings and languages, proof techniques.
Finite automata	Regular languages, finite automata, nondeterminism, regular expressions, pumping lemma.
Pushdown automata	Context-free languages, pushdown automata, pumping lemma.
Turing machines	Turing machines, recursive and RE languages, algorithms, Church-Turing thesis.
Computability	Decidability, halting problem, reduction, self-referencing, recursion theorem, decidability of logical theories, Turing reducibility.
Complexity theory	Time and space complexity, complexity classes P, NP, NP-complete and PSPACE, intractability.

Recommended text

The following book will be mostly followed in the course:

Michael Sipser, Introduction to the Theory of Computation, Thomson Asia Pte Ltd, Singapore, 2001. A second edition of the international edition of the book is published in February 2005. It is not clear whether Indian/Asian reprint of this second edition is available.

Test papers

• Class test 1: September 08, 2005, 09:30-10:30
  Questions [pdf, ps]    Solutions [pdf, ps]

• Mid-Sem test: September 19, 2005, 09:00-11:00
  Questions [pdf, ps]    Solutions [pdf, ps]

• Class test 2: November 14, 2005, 09:30-10:30
  Questions [pdf, ps]    Solutions [pdf, ps]

• End-Sem test: November 23, 2005, 14:00-17:00
  Questions [pdf, ps]    Solutions [pdf, ps]