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

 Course: B.E Computer Science and Engineering University/board:

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 CIRCUIT-VALUE is p-complete?
17. What are the classes L and NL?
18. Define EXSPACE-complete.
19. Give the proof idea for FORMULA-GAME is PSPACE-complete.
20. Define PSPACE and PSPACE-complete?

PART - B
ANSWER ANY FIVE QUESTIONS (5 X 12 = 60 MARKS )

21.(i) Give implementation-level 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 Turing-recognizable 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 Turing-recognizable.(6)

24.(i) Prove that HALT(TM) is decidable.(6)
(ii) Prove that EQ(TM) is neither Turing-recognizable nor Co-Turing-recognizable.(6)

25. Prove that HAMPATH is NP-complete.

26.(i) Prove that every CFL is a member of P.(8)
(ii) Show that SUBSET-SUM 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 NP-complete.(4)

****THE END****

### Related Question Papers:

• Probability and Queuing theory

• Probability and Queuing theory

• B.E.(Fifth Semester) EXAMINATION,June,2009 DATA COMMUNICATION

• B.E.(Fifth Semester) EXAMINATION,June,2010 DATA COMMUNICATION

• B.E.(Fourth Semester) EXAMINATION,Dec.,2010 OBJECT ORIENTED TECHNOLOGY

• ### Categories

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.

 Join Group