Given an array A$=[4,1,10,9,7,12,8,2,15],$

RANDOMIZED$-$SELECT$($A$,1,9,6)$ will create a series of partitions until the desired order statistics is

found. In the worst scenario, how many partitions will be created and what are these partitions? Please

write down these partitions one by one in the following iterations when performing RANDOMIZED$-$

SELECT$($A$,1,9,6)$ in the worst scenario.

In total, this procedure will create $\_\_\_\_\_\_\_\_($how many$)$ partitions in the worst scenario.

$1$st iteration, the partition created is: $[1,4,10,9,7,12,8,2,15]$

$2$nd iteration, the partition created is: $[\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_]$

$3$rd iteration, the partition created is: $[\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$ Question $2.(25$ points in total$)($both CSCE $423$ and CSCE $823)$ Minimum Spanning Tree.

Given the following graph and pseudo$-$codes:

$```$

MST$-$Prim$($G$,$w$,$r$)$

for each u $\backslash$inG$.$V

u$.$key $==$

u$.\backslash$pi$=$ NIL

r$.$key $=0$

Q $=$ G$.$V

while Q

eq$\backslash$emptyset

u$=$Extract$-$Min$\}($Q

for each v$\}\backslash$inG$.$Adj$[$u

if v$\backslash$inQ and w$($u$,$v$)$