In an alternate reality, the $417$ staff are deciding where to travel to escape from their weekly duties. Robbie really

wants to go to Chicago but he$$s willing to change his mind, provided that more than $2/3$ of the TAs can agree on a

different place. Before starting the discussion, every TA writes up a Location Proposal detailing their ideal travel

spot.

$$ If more than $2/3$ of the TAs agree exactly on what place to visit, then Robbie is out of luck.

$$ Otherwise, the staff will travel to Chicago.

More formally, you have an array of n Locations $($called proposals$).$ You can call $.$equals$()$ on two Locations, but

it takes a long time. Even worse, there$$s no $.$compareTo$()$ implemented, nor a $.$hashcode$().$ So you can$$t sort these

Objects, nor put them in a hash table.

In the case that more than $2/3$ of the TAs submit equal Location Proposals, you should return that Location.

Otherwise, you should return Location.RobbieFavorite.

In this problem, you$$ll describe a divide$-$and$-$conquer algorithm that requires O $($t $$ n log n$)$ time.

For simplicity, you may assume that the number of elements in the array is a power of $2.$

$($a$)$ Write pseudocode $($or English$)$ for your algorithm. Your algorithm must use divide and conquer. There are

other $($possibly more efficient$)$ algorithms that aren$$t divide and conquer, but they are not permitted for this

question $($we want you to practice the new technique$).$

$($b$)$ Prove the following implication: If more than $2/3$ of the TAs agree on a location, then in at least one of the

two subarrays more than $2/3$ of the TAs agree on a location. For simplicity, you may assume the number of

elements is a multiple of $6.$

$($c$)$ Write a recurrence to describe the running time of your algorithm. When analyzing running time, assume that

any call to $.$equals$()$ will take t time. You should treat t as a variable in your running$-$time analysis of this

problem $($i$.$e$.$ don$$t consider it a constant and have it $$disappear$$ in the O$-$notation$).$ Briefly $(1-2$ sentences$)$

justify your recurrence. You should convince yourself that the running time will be O $($t $$ n log n$),$ but you

don$$t have to include that explanation.