THEORY OF COMPUTATION Anna University Coimbatore Syllabus
UNIT I Church-Turing thesis: Turing machines – Variants of Turing Machines – Hilbert’s problems. Decidability: Decidable languages – Halting problem.
UNIT II 9
Reducibility: Undecidable problems from Language theory – A simple Undecidable problem – Mapping Reducibility. Advanced topics in Computability Theory: The Recursion Theorem – Decidability of logical theories – Turing Reducibility.
Time Complexity: Measuring Complexity – The Class P – The class NP – NPcompleteness – Additional NP-complete Problems.
UNIT IV 9
Space Complexity: Savitch’s Theorem – The Class PSPACE – PSPACE-completeness – The classes L and NL – NL-completeness – NL equals coNL. Intractability: Hierarchy Theorems – Relativization – CircuitComplexity.
Advanced topics in complexity theory: Approximation Algorithms – Probabilistic Algorithms – Alternation – Interactive Proof Systems – Parallel Computation – Cryptography
1. Michael Sipser, Introduction to the Theory of Computation, Thomson Brook/cole, 1997.(2006)
2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, 3/E, Pearson Education, 2009.
1. Peter Linz, An Introduction to formal Languages and Automata, 4/ E, Jones & Bartlett Pub, 2006.
2 Kamala Krithivasan, Rama R, Introduction to Formal Languages, Automata Theory and Computation, Pearson, 2009
3. Dr. B. N. Srinivasa Murthy, Formal Languages and Automata Theory, Sanguine Publishers, 2006.
THEORY OF COMPUTATION Anna University Coimbatore Syllabus Reviewed by Rejin Paul on 4:15 PM Rating: