George Mason University Use of Randomized Selection Algorithm Java Program

We are given a sequence of n numbers a1, a2, . . . , an. Your task is to determine twothings: (1) whether there exists an integer x that occurs in the sequence more than n/2times, and (2) whether there exists an integer x that occurs in the sequence more than n/3times. See the example in the file input-4.1.txt and the answers in the file answer-4.1.txt.Design an algorithm that runs in time O(n) using the Randomized Selection algorithm -see Section 9.2 in the textbook.

Hint: Using Randomized Select, you can find a single “suspect” for the number thatmay appear n/2 times (think about a connection to the median of the array). Once youhave a suspect, you can verify if it actually appears n/2 times or not by doing one passthrough the area to count the number of appearances.

For the second part with n/3 appearances, using Randomized Select, you can find twopossible “suspects”, and then check each one of them

(Note: since the algorithm is randomized, the O(n) bounds the expected running time).

Input specification: The input contains two lines. The first line contains n and thesecond line contains the integers a1, a2, . . . , an, separated by spaces. You may assume thatall numbers fit within int and that n is not bigger than 10,000,000.

Output specification: The output contains two lines containing as answers to the twoquestions the strings ”YES” or ”NO” (see the sample outputs below) .