Download Model question papers & previous years question papers

Posted Date: 18 Apr 2011      Posted By:: kavyya    Member Level: Bronze    Points: 5 (Rs. 1)

2011 Anna University of Technology Coimbatore 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





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****





Return to question paper search

Next Question Paper: Textile Science

Previous Question Paper: Data structure and File Processing

Related Question Papers:


  • Probability and Queuing theory


  • Probability and Queuing theory


  • Probability and Random Process-Model Question paper


  • Generation transmission and distribution


  • Principles of communication


  • 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.

    Awards & Gifts
    Active Members
    TodayLast 7 Daysmore...

    Online Members

    Phagu Mahato
    More...
    ISC Technologies, Kochi - India. Copyright © All Rights Reserved.