Download Model question papers & previous years question papers
Posted Date: 18 Apr 2011 Posted By:: kavyya Member Level: Bronze Points: 5 (Rs. 1)

2011 B.E Computer Science and Engineering Theory of computation(080230026) Question paper
ANNA UNIVERSITY OF TECHNOLOGY , COIMBATORE B.E / B.TECH DEGREE EXAMINATIONS: APRIL / MAY 2011 REGULATIONS : 2008 SIXTH SEMESTER  CSE 080230026  THEORY OF COMPUTATION
TIME : 3 Hours Max.Marks:100 PART  A ANSWER ALL QUESTIONS (20 * 2 =40 MARKS) 1. What is Turing machine? 2. Give the difference between FA and TM. 3. Define Multitape Turing Machine. 4. What is meant by halting problem? 5. What is Mapping reducibility? 6. Define Turing reducible. 7. Give the definition of linear bound automaton. 8. Find a match in the following instance of PCP. {[ab/abab],[b/a],[aba/b],[aa/a]} 9. What is Time complexity? 10. Define class P and NP completeness. 11. Prove that CLIQUE is in NP. 12. State the True or False for the following statement (i) n^2=o(log^2 n) (ii) nlogn=o(n^2) 13. Define Probabilistic Turing machine. 14. Define trapdoor function. 15. What is one  way permutation? 16. Prove that CIRCUITVALUE is pcomplete? 17. What are the classes L and NL? 18. Define EXSPACEcomplete. 19. Give the proof idea for FORMULAGAME is PSPACEcomplete. 20. Define PSPACE and PSPACEcomplete?
PART  B ANSWER ANY FIVE QUESTIONS (5 X 12 = 60 MARKS )
21.(i) Give implementationlevel description of Turing machines that decide the following language over the alphabet{0,1} (a) {w/w contains an equal number of 0s and 1s}. (8) (ii) Show that a language is Turingrecognizable if and only if some enumerators enumerates it.(4)
22.(i) Prove that every CFL is decidable.(6) (ii) Show that EQ(DFA) is a decidable language.(6)
23.(i) Prove that Recursive theorem.(6) (ii) Show that MIN(TM) is not Turingrecognizable.(6)
24.(i) Prove that HALT(TM) is decidable.(6) (ii) Prove that EQ(TM) is neither Turingrecognizable nor CoTuringrecognizable.(6)
25. Prove that HAMPATH is NPcomplete.
26.(i) Prove that every CFL is a member of P.(8) (ii) Show that SUBSETSUM is in NP.(2) (iii) Give the comparison of P versus NP.(2)
27.(i) Prove that NL is a subset of NC^2.(6) (ii) Show that if P is an odd prime number Pr[PRIME accepts P]=1.(6)
28.(i) Prove that Savitch's theorem.(8) (ii) Show that 3SAT is NPcomplete.(4)
****THE END****
Return to question paper search


Submit Previous Years University Question Papers and
make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.