1. If the number of steps required to solve a problem is O(nk), then the problem is said to be solved in:
a) non-polynomial time
b) polynomial time
c) infinite time
d) none of the mentioned
View Answer
Answer: b
Explanation: Most of the operations like addition, subtraction, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the input and k is some non negative integer.
Explanation: Most of the operations like addition, subtraction, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the input and k is some non negative integer.
2. The hardest of NP problems can be:
a) NP-complete
b) NP-hard
c) P
d) None of the mentioned
View Answer
Answer: a
Explanation: NP class contains many important problems, the hardest of which is NP-complete, whose solution is sufficient to deal with any other NP problem in polynomial time.
Explanation: NP class contains many important problems, the hardest of which is NP-complete, whose solution is sufficient to deal with any other NP problem in polynomial time.
a) PSPACE
b) EXPSPACE
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: It is sufficient to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial time verifier. It is also contained in EXPTIME, since the same algorithm operates in exponential time.
Explanation: It is sufficient to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial time verifier. It is also contained in EXPTIME, since the same algorithm operates in exponential time.
a) incidence matrix
b) bipartite graph
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: c
Explanation: The relation ‘contains’ can be represented using a bipartite graph. The vertices of the graph can be divided into two disjoint sets, one representing the subset S and the other representing the elements of P and one edge for each subset in S;each node is included in exactly one of the edges forming the cover.
Explanation: The relation ‘contains’ can be represented using a bipartite graph. The vertices of the graph can be divided into two disjoint sets, one representing the subset S and the other representing the elements of P and one edge for each subset in S;each node is included in exactly one of the edges forming the cover.
NL? P? NP? PH? PSPACE
a) NP? P? NL? PH? PSPACE
b) NL? PH? NP? P? PSPACE
c) NL? P? NP? PH? PSPACE
d) None of the mentioned
View Answer
Answer: c
Explanation: The given order is the only correct order and further PSPACE belongs to EXPTIME class and subsequently occurs EXPSPACE class.
Explanation: The given order is the only correct order and further PSPACE belongs to EXPTIME class and subsequently occurs EXPSPACE class.
The given relation involves which of the following theorems?
a) Space hierarchy theorem
b) Savitch’s theorem
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: From space hierarchy theorem: NL ? NPSPACE, from Savitch’s theorem: NPSPACE= PSPACE.
Explanation: From space hierarchy theorem: NL ? NPSPACE, from Savitch’s theorem: NPSPACE= PSPACE.
If f=O(h) and g=O(k) for f,g,h,k:N->N, then
a) f+g = O(h+k)
b) fg = O(hk)
c) fg=O(hk)
d) None of the mentioned
View Answer
Answer: c
Explanation: f,g,h,k are partial functions and each is defined at all but a finite number of points.
Explanation: f,g,h,k are partial functions and each is defined at all but a finite number of points.
8. Which of the following is not correct for ZPP?
a) zero error probabalistic polynomial time
b) it runs in non-polynomial time
c) it returns an answer yes, no or do not know
d) none of the mentioned
View Answer
Answer: b
Explanation: ZPP is zero error probabalistic polynomial time complexity class which run in polynomial time, returns an answer: yes, no or do not know.
Explanation: ZPP is zero error probabalistic polynomial time complexity class which run in polynomial time, returns an answer: yes, no or do not know.
a) P=BPP problem
b) NP=co-NP problem
c) Do one way problems exist?
d) All of the mentioned
View Answer
Answer: d
Explanation: There exists a list of unsolved problems in computational theory which includes many problems including the ones given.
Explanation: There exists a list of unsolved problems in computational theory which includes many problems including the ones given.
10. Given: ?= {a, b}
L= {x??*|x is a string combination}
?4 represents which among the following?
a) {aa, ab, ba, bb}
b) {aaaa, abab, e, abaa, aabb}
c) {aaa, aab, aba, bbb}
d) All of the mentioned
View Answer
Answer: b
Explanation: ?* represents any combination of the given set while ?x represents the set of combinations with length x where x ? I.
11. Regular expression for all strings starts with ab and ends with bba is.
a) aba*b*bba
b) ab(ab)*bba
c) ab(a+b)*bba
d) All of the mentioned
View Answer
Answer:c
Explanation: Starts with ab then any number of a or b and ends with bba.
Explanation: Starts with ab then any number of a or b and ends with bba.
a) 16
b) 26
c) 32
d) 64
View Answer
Answer:d
Explanation: Number of DFA’s = 2n * n(2*n).
Explanation: Number of DFA’s = 2n * n(2*n).
a) NFA is slower to process and its representation uses more memory than DFA
b) DFA is faster to process and its representation uses less memory than NFA
c) NFA is slower to process and its representation uses less memory than DFA
d) DFA is slower to process and its representation uses less memory than NFA
View Answer
Answer: c
Explanation: NFA, while computing strings, take parallel paths, make different copies of input and goes along different paths in order to search for the result. This creates the difference in processing speed of DFA and NFA.
Explanation: NFA, while computing strings, take parallel paths, make different copies of input and goes along different paths in order to search for the result. This creates the difference in processing speed of DFA and NFA.
a) 5
b) 6
c) 7
d) 4
View Answer
Answer: a
Explanation: For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.
Explanation: For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method
View Answer
Answer: c
Explanation: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.
Explanation: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.
