n this assignment, you will apply the Divide and Conquer technique to develop an effi

$-$

cient algorithm that solves the following

$$

popularity

$$

$$problem:

The input for this problem is a sorted

$($

sub

$)$

$$list of integers A

$=$

$[$

al

$,$

$$al

$+$

$1$

$,$

$.$

$.$

$.$

$,$

$$ar

$]$

$$with

al

$<$

$=$

$$al

$+$

$1$

$<$

$=$

$$

$$

$$

$<$

$=$

$$ar

$.$

$$Note that, assuming array indices start at

$1$

$,$

$$we have

$1$

$<$

$=$

$$l

$<$

$=$

$$r

and we define N

$=$

$$r

$$

$$l

$+$

$1$

$.$

An element in such a

$($

sub

$)$

$$list A is said to be popular if it occurs at least as often as

any other element in A

$.$

The output for this problem is the

$($

value of a

$)$

$$popular element. Notice that we do not

require the output to be the popular element, because, unlike in the majority element prob

$-$

lem, a popular element need not be unique. When multiple popular elements exist, then any

popular element is a valid output. Specify the steps of your algorithm. You don

$$

t have to formally prove your

algorithm is correct, but it would be a good idea for you to do so using strong mathe

$-$

matical induction

$($

it would be good practice

$)$

$.$

Your algorithm must:

$1$

$.$

$$be a valid divide and conquer algorithm, where each recursive call processes a sub

list whose size is roughly half that of the given sub list,

$2$

$.$

$$return a valid popular element in the given input list for any valid input list,

$3$

$.$

$$use O

$($

$1$

$)$

$$additional space, not counting the implicit space used by the call stack

$($

so

$,$

$$just local variables, and no extra auxiliary data structures of any kind

$)$

$,$

$4$

$.$

$$not modify the given input list,

$5$

$.$

$$not use any repetition

$($

loop

$)$

$$structures$,$ and

$6$

$.$

$$have best case running time O

$($

$1$

$)$

$.$

You may assume that Count

$($

x

$,$

$$A

$=$

$[$

al

$,$

$$al

$+$

$1$

$,$

$.$

$.$

$.$

$,$

$$ar

$]$

$)$

$$returns the number of occurrences

of x in A and its worst case running time is O

$($

f

$($

N

$)$

$)$

$,$

$$where N

$=$

$$r

$$

$$l

$+$

$1$

$.$

$$You must

use Count in your solution.

I

$$

ll get you started with certain parts of the algorithm, and you fill in the missing details.

Your algorithm must achieve best case running time O

$($

$1$

$)$

$.$

Popular

$-$

Sorted

$($

A

$=$

$[$

al

$,$

$$al

$+$

$1$

$,$

$.$

$.$

$.$

$,$

$$ar

$]$

$)$

:

if l

$=$

$$r then

$?$

$?$

$?$

end if

Let m

$=$

$$l

$+$

r

$2$

$,$

$$AL

$=$

$[$

al

$,$

$$al

$+$

$1$

$,$

$.$

$.$

$.$

$,$

$$am

$]$

$$and AR

$=$

$[$

am

$+$

$1$

$,$

$$am

$+$

$2$

$,$

$.$

$.$

$.$

$,$

$$ar

$]$

Put the rest of your pseudocode on the next page. import java.util.$*$;

public class PopularSortedAlgorithm $\{$

public static void main$($String$[]$ args$)\{$

$\}$

static $>$ T popularSorted$($ArrayList data$)\{$

$//$ You may assume data $!=$ null

$//$ Must only call popularSortedHelper.

$\}$

static $>$ T popularSortedHelper$($ArrayList data,

int left,

int right$)\{$

$//$ Recursive helper method

$//$ Must only call popularSortedHelper and count.

$\}$

static $>$ int count$($T target,

ArrayList data,

int left,

int right$)\{$

$//$ Return how many times x occurs within data$[$left $...$ right$]$

$//$ May only $($but isn't required to$)$ call itself, but not any other methods.

$\}$

$\}$