Anna University -Study Materials for all Departments Latest News

080230026 Theory of Computation CSE 6th Semester Anna University Coimbatore Syllabus Regulation 2008

Anna university Coimbatore Syllabus

080230026 Theory of Computation CSE 6th Semester Anna University Coimbatore Syllabus Regulation 2008

Department of Computer science and Engineering 

Meant for Anna University Coimbatore,trichy,trinelveli

(Regulation 2008/2010)
University:Anna University
Year: third  Year
Department: B.E Computer Science and Engineering 
Semester:  (VI) 
Content: 080230026 Theory of Computation CSE 6th Semester Anna University Coimbatore Syllabus Regulation 2008
Subject code: 080230026
Subject Name: Theory of Computation
Regulation: 2008 or 2010 
Post Type: Syllabus


Church-Turing thesis: Turing machines Variants of Turing Machines Hilbert’s problems. Decidability: Decidable languages Halting problem.

UNIT II                                                                                                                        

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.

UNIT III                                                                                                                       

Time Complexity: Measuring Complexity The Class P The class NP NP- completeness Additional NP-complete Problems.

UNIT  IV                                                                                                                                  

Space Complexity: Savitch’s Theorem The Class PSPACE PSPACE-completeness
The classes L and NL NL-completeness NL equals coNL. Intractability: Hierarchy
Theorems Relativization Circuit Complexity.

UNIT  V                                                                                                                                  

Advanced topics in complexity theory: Approximation Algorithms Probabilistic Algorithms – Alternation Interactive Proof Systems Parallel Computation – Cryptography
TOTAL : 60

1.  Michael Sipser, Introduction to the Theory of Computation, Thomson Brook/cole,
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.

Like our Facebook Page to get regular Updates


For All Subject Syllabus-Download Link

For All Subject Question Papers -Download Link

Related Searches:
Anna University Coimbatore CSE syllabus
Anna University Coimbatore CSE  6th semester syllabus
Cse syllabus for Anna university coimbatore
080230026 Theory of Computation Syllabus
Syllabus for 080230026
Syllabus for Theory of Computation
Affiliated institutions CSE 6th sem AU coimbatore syllabus
BE cse syllabus for anna university coimbatore
AU coimbatore cse syllabus
AU coimbatore cse fifth semester syllabus
CSE fifth semester syllabus for Anna university coimbatore
Share on Google Plus
    Blogger Comment


Post a Comment