Automata Theory Questions and Answers – Randomized Algorithm

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Randomized Algorithm”

1. 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 mentioned
View Answer

Answer: c
Explanation: 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.

2. Which of the following options match the given statement:
Statement: The algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time.
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) None of the mentioned
View Answer

Answer: a
Explanation: The other type of algorithms are probabalistic algorithms, which depending upon the random input, have a chance of producing incorrect results or fail to produce a result.

3. Which of the following are probalistic algorithms?
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) All of the mentioned
View Answer

Answer: d
Explanation: Monte Carlo algorithms are very vast, but only probably correct. On thr other side, Las Vegas algorithms are always correct, but probably fast.
advertisement
advertisement

4. 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 mentioned
View Answer

Answer: c
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.

5. Prisonner’s dilemma can be related to the following:
a) cooperative behaviour
b) graph theory
c) all of the mentioned
d) None of the mentioned
View Answer

Answer: a
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.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Unix sort command uses _________ as its sorting technique.
a) Quick Sort
b) Bucket Sort
c) Radix Sort
d) Merge Sort
View Answer

Answer: a
Explanation: Quicksort is the method of choice in many applications( Unix sort command) with O(nlogn) in worst case.

7. State true or false:
Statement: A turing machine has the capability of using randomly ‘generated’ numbers.
a) true
b) false
View Answer

Answer: a
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.
advertisement

8. For the given algorithm, find the probability of finding after k iterations:

find_a(array A, n, k)
begin
   i=0
     repeat
           Randomly select one element out of n elements
           i=i+1
     until i=k or a is found
end

a) (1/2)k
b) (1-(1/3))k
c) 1-(1/2)k
d) None of the mentioned
View Answer

Answer: c
Explanation: The given is known as Monte Carlo Algorithm. If a is fount, the algorithm succeeds, else the algorith fails. The algorithm doesn not guarantee success but the run time is bounded.
advertisement

9. 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 mentioned
View Answer

Answer: d
Explanation: There exists a list of unsolved problems in computational theory which includes many problems including the ones given.

10. Which of the following can be referred to as applications of Randomized algorithm?
a) Quicksort
b) Min Cut
c) Verifying Matrix Multiplication
d) All of the mentioned
View Answer

Answer: d
Explanation: Freivalds algorithm is a probabalistic randomized algorithm we use to verify matrix multiplication. On the other hand, Randomness can be useful in quicksort. If the algorithm selects pivot element uniformaly at random, it has a probably high probabilty of finishing the work in O(nlogn) time regardless of the input.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.