Consider the following problem: Given an unsorted array of numbers A[1], A[2], . . . , A[n], find an element x in A such that rank(x) n/10 Now consider the following algorithm for this problem:

RandomizedApproximateMiddle(A) { 

 pick an element x of A uniformly random; 

return x; }

(a) (4 points) Is this a Las Vegas or a Monte Carlo algorithm? Why?

(b) (6 points) What is the probability that the RandomizedApproximateMiddle would return a correct answer?