22 + Interview Questions in Other Classes Of Problems in Automata Theory Page 1 InterviewSolution

1.	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 mentionedI have been asked this question in semester exam.This is a very interesting question from Class RP and ZPP,Complexity topic in chapter Other Classes Of Problems of Automata Theory
Answer» The correct option is (b) it RUNS in non-POLYNOMIAL time To explain I would say: ZPP is ZERO error probabalistic polynomial time complexity class which RUN in polynomial time, returns an answer: yes, no or do not know.

Discussion

2.	Which of the following are basic complexity classes for a function f:N->N?(a) Ntime(f)(b) Nspace(f)(c) Space(f)(d) All of the mentionedI have been asked this question in exam.Query is from Class RP and ZPP,Complexity in section Other Classes Of Problems of Automata Theory
Answer» The correct ANSWER is (d) All of the mentioned Easy explanation: Ntime(f): is a set of languages that can be ACCEPTED by a NTM T with NON deterministic time COMPLEXITY function t <=f. In all four cases, the machines are allowed to be multitape TM’s.

Discussion

3.	Which of the following algorithms are probably correct as well as fast?(a) Las Vegas Algorithm(b) Monte Carlo Algorithm(c) Atlantic City Algorithm(d) All of the mentionedI had been asked this question in an internship interview.Enquiry is from Randomized Algorithm topic in section Other Classes Of Problems of Automata Theory
Answer» RIGHT answer is (c) Atlantic CITY Algorithm Easiest EXPLANATION: The atlantic city algorithms which are bounded polynomial time algorithms are probably CORRECT and probably fast. It is correct more than 75% of the times.

Discussion

4.	A function f is called __________ if there exists a TM T so that for any n and any input string of length n, T halts in exactly f(n) moves.(a) Step function(b) Step counting function(c) Inplace functions(d) None of the mentionedI had been asked this question in an online interview.Question is taken from Class RP and ZPP,Complexity in division Other Classes Of Problems of Automata Theory
Answer» Correct ANSWER is (b) Step counting FUNCTION Easiest explanation: If f is a step counting function, T is a TM HALTING in f(n) MOVES where n is the length of input STRING.

Discussion

5.	State true or false:Statement: A turing machine has the capability of using randomly ‘generated’ numbers.(a) Statement: A turing machine has the capability of using randomly ‘generated’ numbers.(b) true(c) falseThis question was addressed to me at a job interview.This key question is from Randomized Algorithm topic in chapter Other Classes Of Problems of Automata Theory
Answer» Correct option is (a) Statement: A turing machine has the capability of USING randomly ‘generated’ numbers. The explanation: Complexity theories models randomized ALGORITHMS as probalistic turing MACHINES. A probalistic turing machine is a non DETERMINISTIC turing machine which randomly chooses between the available transitions at each point according to some probalistic distribution.

Discussion

6.	Which of the following are probalistic algorithms?(a) Las Vegas Algorithm(b) Monte Carlo Algorithm(c) Atlantic City Algorithm(d) All of the mentionedThe question was asked in an online quiz.This interesting question is from Randomized Algorithm topic in division Other Classes Of Problems of Automata Theory
Answer» The correct ANSWER is (d) All of the mentioned Explanation: MONTE Carlo ALGORITHMS are very vast, but only probably correct. On thr other SIDE, LasVegas algorithms are always correct, but probably fast.

Discussion

7.	Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.(a) time(b) space(c) both time and space(d) none of the mentionedThis question was addressed to me in an internship interview.The query is from PSPACE topic in division Other Classes Of Problems of Automata Theory
Answer» The CORRECT choice is (b) SPACE To explain: Though it may USE extra time, but as PSPACE=NPSPACE from savitch’s theorem, we can say that space taken is same for both the machins, DETERMINISTIC as WELL as non-deterministic.

Discussion

8.	Which among the following is smallest for n=50(a) 2n2(b) n2+3n+7(c) n3(d) 2nThis question was posed to me at a job interview.Enquiry is from Class RP and ZPP,Complexity topic in portion Other Classes Of Problems of Automata Theory
Answer» RIGHT OPTION is (B) n2+3n+7 The best I can explain: 2n2=5000 n2+3n+7=2567 n3=125000 2n=1.13*1015

Discussion

9.	A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.(a) worst case(b) best case(c) average case(d) none of the mentionedThis question was posed to me in an online interview.The query is from Randomized Algorithm in portion Other Classes Of Problems of Automata Theory
Answer» The correct answer is (c) average CASE To explain: A randomized algorithm is an algorithm that EMPLOYS a degree of randomness as a part of its logic USING random bits as inputs and in hope of producing average case good PERFORMACE.

Discussion

10.	Complement of all the problems in PSPACE is ________(a) PSPACE(b) NL(c) P(d) All of the mentionedI had been asked this question during an interview for a job.I need to ask this question from PSPACE in division Other Classes Of Problems of Automata Theory
Answer» RIGHT CHOICE is (a) PSPACE The explanation: The complement of all the problems in PSPACE are ALSO in PSPACE, meaning co-PSPACE= PSPACE.

Discussion

11.	The space complexity of a turing machine is undefined if:(a) It is a multitape turing machine(b) If no string of length n causes T to use infinite number of tape squares(c) If some input of length n causes T to loop forever(d) None of the mentionedI got this question during an online interview.Question is taken from Class RP and ZPP,Complexity in division Other Classes Of Problems of Automata Theory
Answer» Right choice is (C) If some INPUT of LENGTH n causes T to loop forever The best explanation: If there exists an input string of length n that causes T to use an infinite number of tape squares, the space complexity of the TURING machine is UNDEFINED.

Discussion

12.	All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:(a) PSPACE(b) NPSPACE(c) EXPSPACE(d) None of the mentionedThis question was addressed to me in exam.I need to ask this question from PSPACE topic in division Other Classes Of Problems of Automata Theory
Answer» Correct OPTION is (a) PSPACE The best I can explain: PSPACE is the PROBLEM class which contains all SET of decision problems which can be SOLVED using a turing machine taking POLYNOMIAL amount of space.

Discussion

13.	Which of the following can be solved in computer science?(a) P=BPP problem(b) NP=co-NP problem(c) Do one way problems exist?(d) All of the mentionedI had been asked this question in examination.Question is taken from Randomized Algorithm topic in division Other Classes Of Problems of Automata Theory
Answer» CORRECT choice is (d) All of the mentioned Explanation: There EXISTS a LIST of unsolved problems in computational theory which includes many problems including the ONES GIVEN.

Discussion

14.	The class PSPACE is closed under the following operations:(a) Union(b) Concatenation(c) Kleene(d) All of the mentionedI got this question in a national level competition.Origin of the question is PSPACE topic in portion Other Classes Of Problems of Automata Theory
Answer» Correct choice is (d) All of the mentioned For explanation: The CLOSURE PROPERTY of PSPACE class includes :- UNION, Concatenation and KLEENE operation.

Discussion

15.	Statement : All PSPACE problems can be reduced to PSPACE-complete problems.(a) State true or false:(b) true(c) falseThis question was addressed to me at a job interview.The question is from PSPACE in division Other Classes Of Problems of Automata Theory
Answer» Correct answer is (a) STATE true or false: EASY explanation: PSPACE-complete problems are the most difficut problems is PSPACE. Finding a simple SOLUTION to PSPACE-complete means simple solution to all other problems in PSPACE because all PSPACE problems can be REDUCED to PSPACE-complete problems.

Discussion

16.	Prisonner’s dilemma can be related to the following:(a) cooperative behaviour(b) graph theory(c) Both (a) and (b)(d) None of the mentionedI got this question in an interview for job.The question is from Randomized Algorithm in division Other Classes Of Problems of Automata Theory
Answer» Right option is (a) cooperative behaviour Explanation: Prisonner’s dilemma is a standard example of a GAME analysed in game theory where rational cooperative behaviour is judged on the basis of REWARDS and PUNISHMENT.

Discussion

17.	ZPP is exactly equal to the ____________of the classes RP and co-RP.(a) Union(b) Intersection(c) Concatenation(d) DifferenceI got this question in unit test.I would like to ask this question from Class RP and ZPP,Complexity in section Other Classes Of Problems of Automata Theory
Answer» The correct choice is (B) Intersection The EXPLANATION is: To prove the following statement, we need to take in NOTE that every problem in RP and co-RP has a Las-Vegas ALGORITHM.

Discussion

18.	ZPP is based on ________(a) Probabalistic turing machine(b) Alternative turing machine(c) Quantum turing machine(d) None of the mentionedThe question was asked during an online exam.The question is from Class RP and ZPP,Complexity topic in chapter Other Classes Of Problems of Automata Theory
Answer» Right OPTION is (a) Probabalistic turing machine The best I can explain: A probabalistic turing machine is a NON deterministic turing machine which randomly chooses between the available transitions at each point according to some PROBABILITY DISTRIBUTION.

Discussion

19.	Unix sort command uses _________ as its sorting technique.(a) Quick Sort(b) Bucket Sort(c) Radix Sort(d) Merge SortThe question was asked during an internship interview.My doubt stems from Randomized Algorithm topic in section Other Classes Of Problems of Automata Theory
Answer» RIGHT option is (a) Quick Sort The best I can explain: Quicksort is the METHOD of CHOICE in many applications( Unix sort command) with O(nlogn) in worst CASE.

Discussion

20.	Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)(a) O(nf)(b) O(n+f)(c) O(n^2f^2)(d) None of the mentionedThe question was asked by my school teacher while I was bunking the class.Origin of the question is Class RP and ZPP,Complexity in chapter Other Classes Of Problems of Automata Theory
Answer» Right answer is (c) O(n^2f^2) Explanation: Using the encoding function, it is possible to show that if the function F is a STEP COUNTING function, then the function Cn^2(f(n))^2 is the total NUMBER of moves required.

Discussion

21.	PSPACE is strictly the super set of:(a) Regular language(b) Context free language(c) Context Sensitive Language(d) None of the mentionedI have been asked this question by my school principal while I was bunking the class.Question is from PSPACE in section Other Classes Of Problems of Automata Theory
Answer» Right ANSWER is (c) Context Sensitive Language To ELABORATE: Membership of a string in a language defined by an arbitrary context sensitive GRAMMAR, or by an arbitrary determinisic context sensitive grammar, is a PSPACE -COMPLETE problem.

Discussion

22.	Savitch theorem relates to which of the following:(a) PSPACE=NPSPACE(b) Alternating Turing Machine(c) Time complexity(d) None of the mentionedI have been asked this question by my school principal while I was bunking the class.I would like to ask this question from PSPACE topic in chapter Other Classes Of Problems of Automata Theory
Answer» RIGHT choice is (a) PSPACE=NPSPACE To explain: Some important CONCLUSIONS of Savitch THEOREM includes: a) PSPACE=NPSPACE: square of a POLYNOMIAL function is still a polynomial function. b) NL∈L2

Discussion

Explore topic-wise InterviewSolutions in .

Which of the following are basic complexity classes for a function f:N->N?(a) Ntime(f)(b) Nspace(f)(c) Space(f)(d) All of the mentionedI have been asked this question in exam.Query is from Class RP and ZPP,Complexity in section Other Classes Of Problems of Automata Theory

Which among the following is smallest for n=50(a) 2n2(b) n2+3n+7(c) n3(d) 2nThis question was posed to me at a job interview.Enquiry is from Class RP and ZPP,Complexity topic in portion Other Classes Of Problems of Automata Theory

Complement of all the problems in PSPACE is ________(a) PSPACE(b) NL(c) P(d) All of the mentionedI had been asked this question during an interview for a job.I need to ask this question from PSPACE in division Other Classes Of Problems of Automata Theory

The class PSPACE is closed under the following operations:(a) Union(b) Concatenation(c) Kleene(d) All of the mentionedI got this question in a national level competition.Origin of the question is PSPACE topic in portion Other Classes Of Problems of Automata Theory

Statement : All PSPACE problems can be reduced to PSPACE-complete problems.(a) State true or false:(b) true(c) falseThis question was addressed to me at a job interview.The question is from PSPACE in division Other Classes Of Problems of Automata Theory

Prisonner’s dilemma can be related to the following:(a) cooperative behaviour(b) graph theory(c) Both (a) and (b)(d) None of the mentionedI got this question in an interview for job.The question is from Randomized Algorithm in division Other Classes Of Problems of Automata Theory

ZPP is exactly equal to the ____________of the classes RP and co-RP.(a) Union(b) Intersection(c) Concatenation(d) DifferenceI got this question in unit test.I would like to ask this question from Class RP and ZPP,Complexity in section Other Classes Of Problems of Automata Theory

ZPP is based on ________(a) Probabalistic turing machine(b) Alternative turing machine(c) Quantum turing machine(d) None of the mentionedThe question was asked during an online exam.The question is from Class RP and ZPP,Complexity topic in chapter Other Classes Of Problems of Automata Theory

Unix sort command uses _________ as its sorting technique.(a) Quick Sort(b) Bucket Sort(c) Radix Sort(d) Merge SortThe question was asked during an internship interview.My doubt stems from Randomized Algorithm topic in section Other Classes Of Problems of Automata Theory