With a big election year upon us$2,$ let$$s look at a problem inspired by elections, among others. Imagine that you$$have n voters, and you want to set up k polling places for them to vote at$.$ These polling places should be chosen$$somewhat $$fairly$.$ There are m candidate locations from which the k places are chosen, and we will assume$$that m $<=$ n$.$ The idea is to choose k places so that each is $$convenient$$ for n$/$k voters. $($To avoid annoying$$details$,$ we assume here that k$|$n$.)$ The input to the problem is an n $\backslash$times m matrix of all the distances di$,$j $>0$between voters and polling places: di$,$j is the distance from voter i to polling place j$.$ We will assume that no$$two distances in the matrix are the same$\mathrm{.}3$There are of course many precise formulations of this problem, and many algorithms to choose k polling places;$$one very reasonable algorithm $($which happens to have some useful fairness notions, but we will not focus on$$those here$)$ is Algorithm $3.$ You might want to execute it by hand on paper by drawing circles which gradually$$get bigger, to see how it works.$$Algorithm $3$ POLLING PLACE SELECTION$$Initially$,$ all voters are active, and all polling places are unopened.$$The time t increases continuously.$$At time t$,$ each active voter i is assigned temporarily to all unopened polling places j at distance t or less from i$.$if an unopened polling place j has at least n$/$k voters assigned to it then$$Open that polling place j$.$Make those n$/$k voters inactive.$$Keep doing this, increasing t continuously, until no more voters are active.$$Obviously$,$ this algorithm is phrased informally, using many types of $$commands$$ that you don$$t have in normal$$programming languages. This question is about implementing it precisely and efficiently.$2$Hopefully, you all plan to vote.$3$This should be true if you measure distances in micrometers.$3($a$)$ We wrote $$Open that polling place j$.$ You might legitimately worry that the algorithm is underspecified$$if there are multiple polling places j$,$ j$$ that each reach n$/$k voters at exactly the same time t$.$ Explain why$$this is not a concern here.$($b$)$ As we said above, the description about continuously increasing t and looking what happens is not $$programming$$friendly$.$ Here, you are to describe how to implement this algorithm to run in time O$($n$2$ log n$).($See below for the case when you find that difficult.$)$ In doing so$,$ you will almost certainly want to draw on$$multiple algorithms and data structures you learned in CSCI $104,$ as well as some mathematical knowledge$$about logs and other functions.$$You should not give actual code here $$ rather, give pseudo$-$code which a competent CSCI $104$ student$$could easily turn into actual Python$/$C$++$ code. Also, if you use algorithms or data structures from CSCI$104($or CSCI $170),$ you do not need to actually give the code $$ simply say which algorithm or operation$$you are calling $($such as $$Run BFS from node v and store the distances in an array x$.).($c$)$ Explain informally why your detailed algorithm returns the same result as our informal continuous$-$time$$algorithm$.($d$)$ Carefully analyze the running time and show that it is O$($n$2$ log n$).($Note that we are only asking for the$$upper bound of O$($n$2$ log n$)$ here, not a lower bound of $\backslash$Omega $($n$2$ log n$)$ though the latter would be easy to$$prove$.)$ For any algorithms or data structures you learned in CSCI $104,$ you can simply state the running$$times that you were taught and use in your analysis$$ no need to reprove them yourself.$$If there are some parts that you cannot get to run in O$($n$2$ log n$),$ explain which those parts are, what obstacles$$you were facing, and what you would need to make it work. The more parts you can get in O$($n$2$ log n$),$ the$$closer to full credit you will be$.$ If your algorithm runs in O$($n$3),$ you will get partial credit, depending on how$$many key parts are faster.