Question $1$: Selection Revisited $...$

The Order Selection algorithm we saw in class can be a powerful subroutine. Recall that

Select $(A,k)$ allows one to find the $k$ th smallest element of an unsorted array $A($with $n$

elements$)$ in time $O(n).$

Given an $($unsorted$)$ array A with $n$ elements, a frequent element is defined as some $x$ that

appears at least $|$~$\frac{n}{4}$~$|$ times in the array. Describe an algorithm that runs in $O(n)$ time and

finds all the frequent elements $($if they exist$).$ For convenience, you may assume that $n$ is

a multiple of $4.$ Along with pseudocode, provide reasoning showing that your algorithm

returns the correct answer and has $O(n)$ running time.

$[$Hint: Suppose you find the $k$ th smallest element of A for $k=\frac{n}{4},\frac{n}{2},\frac{3n}{4},n.$ Argue that all

"potential" frequent elements must be one of the elements you found.$]$