$(20$ pts$.)$ Majority Element. An array $A[0,$dots,$n-1]$ is said to have a majority element if more than half

of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array

has a majority element, and, if so$,$ to find that element. The elements of the array are not necessarily from

some ordered domain like the integers, and so there can be no comparisons of the form $"$is $A[i]>A[j]?".$

$($Think of the array elements as image files, say.$)$ However you can answer questions of the form: $"$is

$A[i]=A[j]?"$ in constant $O(1)$ time.

$($a$)$ Show that if $x$ is a majority element in the array then $x$ is a majority element in the first half of the array

or in the second half of the array.

$($b$)$ Show how to check in $O(n)$ time if a candidate element $x$ is indeed a majority element.

$($c$)$ Put these observation together to design a divide$-$and$-$conquer algorithm whose running time is $O(nlogn).$

$($Hint: Use the master theorem to analyze its running time.$)$

$($d$)$ We will now design a linear$-$time algorithm. Here's another divide$-$and$-$conquer approach:

Pair up the elements of A arbitrarily, to get $\frac{n}{2}$ pairs. $($If $n$ is odd, we keep the singleton unpaired

element but only to break a potential tie; that is$,$ this element can't be used to overrule a majority.$)$

Look at each pair: if the two elements are different, discard both of them; if they are the same,

keep just one of them.

Let $L$ be the elements left after this procedure. Show that $L$ has at most $|$~$\frac{n}{2}$~$|$ elements, and that if $A$

has a majority element, then $L$ has the same majority element.

$($e$)$ Use parts $($d$)$ and $($b$)$ to design an algorithm for this problem with $O(n)$ running time.