2 – Deterministic Selection

Please find attached.

Q2 Deterministic Selection
20 Points
a) Suppose that the Selection algorithm used groups of 4 instead of 5.
Assume that the input has no duplicates. Define the representative of a group as some
arbitrary value that is larger than two elements and smaller than two elements of the group
(e.g., for 1,4,2,3, a representative could be 2.5).
State the recurrence that we would get for this variant.
Then state the total time complexity.
There is no need to show any derivations.
Useful LaTeX: $$ \frac{n}{k} $$
Enter your answer here
b) Now suppose that we use groups of 6, this time assuming that the representative of a group
is the element that is defined to be the 3rd smallest.
Again, state the recurrence and time complexity.
Enter your answer here
c) For the standard algorithm with groups of 5, describe a situation where the algorithm checks
if the median of representatives has the rank we’re looking for, even though there is no
possibility that this will be true.
Enter your answer here
d) Using groups of 5, suppose that instead of using the median of a group as a representative,
we use the smallest element within the group. Then we calculate the median of
representatives, x. How many elements are guaranteed to be larger than x, and how many will
definitely be smaller than x?
Enter your answer here