CS515THEORY OF COMPUTATION3-0-0-6

Pre-requisites : NIL

Syllabus :
Automata and Languages: finite automata and regular expressions, pushdown automata and context-free grammars, pumping lemmas and closure proprties of regular and context-free languages, non-context-free languages Computability theory: the Church-Turing thesis, Hilbert's problem, decidability, halting problem, reducibility Complexity theory: time and space complexity, Classes P, NP, NP-complete, PSPACE, and PSPACE-complete Intractability: hierarchy theorem, Relativization, Circuit complexity.

Texts :
1. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004.
2. H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981.

References :
1. J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.
2. S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press,2009.
3. C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1994.
4. D. C. Kozen, Theory of Computation, Springer, 2006.
5. D. S. Garey, G. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.