We have been working very hard since 2009 to facilitate in your learning Read More. We can't keep up without your support. Donate Now.
+ Link For Assignments, GDBs & Online Quizzes Solution 
+ Link For Past Papers, Solved MCQs, Short Notes & More 
CS701 Theory of Computation Short Question & Answers
Q1: Show that A_{TM} is not mapping reducible to E_{TM}. 10 marks Spring 2016 – Mid


Q2: Let L_{ALL} = {M is a TM with input alphabet ∑ and L(M)∑*}, prove that L_{ALL} is not Turing recognizable. 10 marks Spring 2016 – Mid


Q3: In the Silly Post Correspondence Problem (SPCP), in each pair the top string has the same length as the bottom string. Show that the SPCP is decidable, 10 marks Spring 2016 – Mid


Q4: Lets recall that a language A is Truing recognizable if there is a TM M such that L(M)=A. 5 marks Spring 2016 – Mid


Q5: Let X be the set{1,2,3,4,5} and Y be the set (6,7,8,9,10}. We describe the functions f:(X>Y) and g:(X>Y) in the following table.
(d). Is g onetoone? (e). Is g onto? (f) Is g a correspondence? Spring 2016 – Mid


Q6: Let B be the set of all infinite sequences over {0,1}. Show that B is uncountable, using a proof by diagonalization. 10 marks Spring 2016 – Mid


Q7: Show that the set of possible statements in TH(N,+,X) is turing recognizable. 10 marks Spring 2016 – Mid


Q8: if ∀Y∃X[R_{1}(x,x,y)], if we assign plus to (a,c,c) whenever a+b=c. if R is (universe) real number then whether the sentence is TRUE, justify you answer. 10 marks Spring 2016 – Mid


Q9: Show that the set of all off all odd integers has onetoone correspondence with the set of all even integers. 5 marks Spring 2016 – Mid


Q10: Show that all positive numbers has onetoone correspondence to real number. 5 marks Spring 2016 – Mid


Q11: if A belong to a language that contains infinity pairs, prove that its uncountable. 5 marks Spring 2016 – Mid


Q12: Consider following instance of PCP. Is it possible to find a match? If YES then give the dominos arrangements, If NO then prove. 5 marks 1/0, 101/1, 1/001 Spring 2016 – Mid


Q13: Show that 234 and 399 are relatively prime or not. 5 marks Spring 2016 – Mid


Q14: Show that some TRUE statements in TH(N,+,X) are not proveable. 10 marks Spring 2016 – Mid


Q15: Is PCP decidable over unary alphabet? 5 marks Spring 2016 – Mid


Q16: Show that A≤_{T}B and B≤_{T}C then A≤_{T}C. 10 marks Spring 2016 – Mid


Q17: Prove that Turing recogniable languages are closed under concatenation. 10 marks Fall 2015 – Mid

Q18: Show that directed Hamiltonian cycle is NPComplete. 10 marks Spring 2016 – Final

Q19: Prove cycle length problem is NLComplete. 10 marks Spring 2016 – Final

Q20: Let CNF_{K} = {<?>  ? is a satisfiable CNFFormula where each variable appears in at most k places}. 15 marks 1. Show that CNF2 ∈ P. 2. Show that CNF3 ∈ NPcomplete. Spring 2016 – Final

Q21: A directed graph is strongly connected if every two nodes are connected by a directed path in each direction. Let STRONGLYCONNECTED = { G is a strongly connected graph}. Show that STRONGLYCONNECTED is NLcomplete. 10 marks Spring 2016 – Final

Q22: Show that A_{LBA} is PSpace Complete. 10 marks Spring 2016 – Final

Q23: Let ADD={(x,y,z)  x,y,z > 0 are binary integers and x+y=z}. Show that ADD ∈ LSPACE. 10 marks Spring 2016 – Final

Q24: Let t(n) be a function where t(n) ≥ n , Show that t(n) time k tape TM has an equivalent O(t^{2}(n)) time single tape TM. 10 marks Spring 2016 – Final

Q25: Show that 3Color problem is in NP Complete. 10 marks Spring 2016 – Final

Q26: Show that E_{DFA} is in NLComplete. 10 marks Spring 2016 – Final

Q27: Graphs G and H are called isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {<g, h=""> G and H are isomorphic graphs}. Show that ISO is in NP. 10 marks Spring 2016 – Final
</g,> 
Q28: Let SETSPLITTING = {<s,c> S is a finite set and C = {C_{1}, ... ,C_{k}} is a collection of subsets of S, for some k > 0, such that elements of S can be colored red or blue so that no C_{i} has all its elements colored with the same. Show that SETSPLITTING is in NP. 10 marks Spring 2016 – Final
</s,c> 
Q29: Find Maxclique in DP. 10 marks Spring 2016 – Final

Q30: Let CONNECTED={G is connected undirected graph}. Show that it is in P. 10 marks Spring 2016 – Final

Q31: Let HALFCLIQUE = { G is an undirected graph having a complete subgraph with at least m/2 nodes, where m is the number of nodes in G}. Show that Half Clique is in NPcomplete. 10 marks Spring 2016 – Final

Q32: Show that, if P = NP, then every language A is in P, except A = ∅ and A = ∑*, is in NPcomplete. 10 marks Spring 2016 – Final

Q33: Let PALADD = {<x, y=""><x, y>  x, y > 0 are binary integers, where x + y is an integer whose binary representation is palindrome}. Show that PALADD ϵ LSPACE. 10 marks Spring 2016 – Final
</x,> 
Tags:
+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)
+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)
+ Click Here to Search (Looking For something at vustudents.ning.com?) + Click Here To Join (Our facebook study Group)© 2020 Created by +M.Tariq Malik. Powered by
Promote Us  Report an Issue  Privacy Policy  Terms of Service
We are usergenerated contents site. All product, videos, pictures & others contents on vustudents.ning.com don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com or Contact us at contact Page with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List  Moderators Group
All Members  Featured Members  Top Reputation Members  Angels Members  Intellectual Members  Criteria for Selection
Become a Team Member  Safety Guidelines for New  Site FAQ & Rules  Safety Matters  Online Safety  Rules For Blog Post
Looking For Something at Site? Search Below
How to Add New Discussion in Study Group ? Step By Step Guide Click Here.
