Answer in detail Q4. [15 points] Each of the following questions is about \"Sele

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 above

Explanation / 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)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.