Answer in detail Q4. [15 points] Each of the following questions is about \"Sele
ID: 3551555 • Letter: A
Question
Answer in detail
Q4. [15 points] Each of the following questions is about "Selection Problem". Please answer each question with your steps to get your answer. RANDOMIZED-SELECT (A, p. r, i) if p r return A[p] a RANDOMIZED- PARTITION (A, p. r) p 1 pivot value is the answer return Alal elseif i k return RANDOMIZED-SELECT( A, p, q 1.i) else return RANDOMIZED-SELECTOA.q 1. r, i k) (1) [5 points] Given the RANDOMIZED-SELECT to find ith smallest element above, write the psuedocode to find ith largest elements by changing the psuedocode aboveExplanation / Answer
RANDOMIZED-SELECT(A,p,r,i)
if p == r
return A[p]
q = RANDOMIZED-PARTITION(A,p,r)
k = q - p +1
if A.length - i -1 == k
return A[q]
elseif i >k
return RANDOMIZED-SELECT(A,p,q-1,i)
else return RANDOMIZED_SELECT(A<q+1,r,i-k)