Anna University Coimbatore 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
6th SEMESTER - CSE
080230026 - THEORY OF calculation

TIME : three Hours Max.Marks:100
PART - A
ans ALL ques. (20 * two =40 MARKS)
1. What is Turing machine?
2. provide the difference ranging from FA and TM.
3. describe Multitape Turing Machine.
4. What is meant by halting problem?
5. What is Mapping reducibility?
6. describe Turing reducible.
7. provide the definition of linear bound automaton.
8. obtain a match in the subsequent instance of PCP.
{[ab/abab],[b/a],[aba/b],[aa/a]}
9. What is Time complexity?
10. describe class P and NP completeness.
11. Prove that CLIQUE is in NP.
12. State the actual or False for the subsequent statement
(i) n^2=o(log^2 n)
(ii) nlogn=o(n^2)
13. describe Probabilistic Turing machine.
14. describe trapdoor function.
15. What is 1 - way permutation?
16. Prove that CIRCUIT-VALUE is p-complete?
17. elaborate the classes L and NL?
18. describe EXSPACE-complete.
19. provide the proof idea for FORMULA-GAME is PSPACE-complete.
20. describe PSPACE and PSPACE-complete?

PART - B
ans ANY 5 ques. (5 X 12 = 60 MARKS )

21.(i) provide implementation-level description of Turing machines that decide the subsequent 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 a few 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) provide 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****

Earning:   Approval pending.