CS30053 Foundations of computing 

 Autumn 2005, L-T-P: 3-0-0, Credits: 3 


Class timings

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


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.


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]