Using the following information, please simulate how MakeRanking behaves on the $W$ given

in the beginning of this question text. It suffices that you list the result of each call to

MergeRankings.

Consider a tennis tournament where each of the $n$ participants $($numbered $1..n)$ plays every

other player exactly once; each such match will result in a victory for one of the players, as

recorded in the table $W[1..n,1..n]$ where $W[i,j]=1$ if player i won the match against player $j,$

and $W[i,j]=0$ otherwise.

Our goal is to produce a ranking of all $n$ players, where a ranking is defined as a list $R[1.q]$

$($with $qn)$ of different players $($each in $1..n)$ such that for all iin$1..q-1,R[i]$ won the match

against $R[i+1].($Such a ranking may be disputed since, e$.$g$.,R_1$ may have lost all matches

except the one against $R[2].)$

To illustrate, let us consider the table $W$ given above.

Then $7,1$ is a ranking $($since player $7$ beat player $1),4,3$ is a ranking, and even

$6,2,5,8$ is a ranking $($since player $6$ beat player $2$ who beat player $5$ who beat

player $8).$

It turns out $($perhaps surprisingly$)$ that there will always exist at least one ranking. This is

due to the fact that it is always possible to merge rankings for two disjoint set of players into

a ranking of the union of those players. For the above matches, we can for example merge

$7,1$ and $4,3$ : not by putting one in front of the other, since neither $7,1,4,3$ nor $4,3,7,1$ are

valid rankings, but into $4,7,1,3.$

We shall now develop a general algorithm, taking a table $W[1.n,1..n]$ as implicit parameter,

for finding a ranking of $n$ players.

We shall first present an auxiliary algorithm MergeRankings that given disjoint rankings

$A[1.p]$ and $B[1..q]($with $0p$ and $0q)$ produces a specific ranking $C[1..p+q]$ such that if

player $x$ is ranked higher than player $y$ in $A$ or in $B$ then $x$ is ranked higher than $y$ in $C.$ The

algorithm is given by the code

MergeRankings $(A[1..p],B[1..q])i,$jlarr

$p,q$ while $i>0$ or $j>0$ if $i=0$

$C[j]larrB[j]$

jlarrj$-1$

else if $j=0$

$C[i]larrA[i]$

ilarri$-1$

else if $)$

$C_{i+j}$larrB$[j]jlarrj$

$-1$

else

$C_{i+j}$larrA$[i]$

ilarri$-1$

We can now write an algorithm MakeRanking that is based on the Divide & Conquer

paradigm, uses MergeRankings, and which constructs a ranking of the players lo$.$ hi$.($When

called with $(1,n),$ MakeRanking thus returns a ranking of all the players.$)$