Automata Theory Multiple Choice Questions 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
Answer: c
Clarification: 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
Answer: a
Clarification: 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
Answer: d
Clarification: Monte Carlo algorithms are very vast, but only probably correct. On thr other side, Las Vegas algorithms are always correct, but probably fast.
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
Answer: c
Clarification: 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) Both (a) and (b)
d) None of the mentioned
Answer: a
Clarification: 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.
6. Unix sort command uses _________ as its sorting technique.
a) Quick Sort
b) Bucket Sort
c) Radix Sort
d) Merge Sort
Answer: a
Clarification: 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
Answer: a
Clarification: 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.
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
Answer: c
Clarification: 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.
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
Answer: d
Clarification: 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
Answer: d
Clarification: 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.