Given the algorithm below for RandomSelect, trace the function by specifying the
ID: 3549958 • Letter: G
Question
Given the algorithm below for RandomSelect, trace the function by specifying the recursive calls to the function:
The inputs are as follows:
A = {24, 15, 7, 10, 8, 30}, i=2, n=6
RandomElement(A) returns an element of A selected at random using the rand function. Assume that the values of rand are:
rand(1,6)=2, rand(1,5)=4, rand(1,4)=3, rand(1,3)=1, and rand(1,2)=2
RandomSelect (A, i, n) {
// Selects the ith-smallest element in set A where n = |A|
if (n==1)
return the one item in A
else
p = RandomElement(A) // a function that returns a random element of A
H = set of elements > p
L = set of elements <= p
if (i <= |L|)
return RandomSelect (L, i, |L|)
else
return RandomSelect (H, i - |L|, |H|)
}
Explanation / Answer
The character ~ mean white space
RandomSelect A = {24, 15, 7, 10, 8, 30}, i=2, n=6
~~~p = A[2]=15 (rand(1,6)=2)
~~~H = {24, 30}
~~~L = {15, 7, 10, 8}
~~~i <= |L|
~~~RandomSelect (L, i, |L|)
~~~RandomSelect A = {15, 7, 10, 8}, i=2, n=4
~~~~~~p = A[3] = 10 (rand(1,4)=3)
~~~~~~H = {15}
~~~~~~L = {7, 10, 8}
~~~~~~i <= |L|
~~~~~~RandomSelect (L, i, |L|)
~~~~~~RandomSelect A = {7, 10, 8}, i=2, n=3
~~~~~~~~~p = A[1] = 7 (rand(1,3)=1)
~~~~~~~~~H = {10, 8}
~~~~~~~~~L = {7}
~~~~~~~~~i > |L|
~~~~~~~~~RandomSelect (H, i - |L|, |H|)
~~~~~~~~~RandomSelect A = {10, 8}, i=1, n=2
~~~~~~~~~~~~p = A[2] = 8 (rand(1,2)=2)
~~~~~~~~~~~~H = {10}
~~~~~~~~~~~~L = {8}
~~~~~~~~~~~~i <= |L|
~~~~~~~~~~~~RandomSelect (L, i, |L|)
~~~~~~~~~~~~RandomSelect A = {8}, i=1, n=1
~~~~~~~~~~~~~~~return element in A
Final result is 8
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.