$($a$)$ For a graph $G,$ consider two edge$-$weight functions $w_1$ and $w_2$ such that

$w_1(e)w_1(e^{\text{'}})Longleftrightarrow{w}_2(e)w_2(e^{\text{'}})$

for all edges $e,e^{\text{'}}$inE. Show that $T$ is an MST wrt $w_1$ iff it is an MST wrt $w_2.($In other words, only the sorted order of the edges matters for the MST$.)$

$($b$)$ Suppose graph $G$ has integer weights in the range $\{1,$cdotsW$\},$ where $W2.$ Let $G_i$ be the edges of weight at most $i,$ and ${}_i$ be the number of components in $G_i.$ Then show that the MST in $G$ has weight exactly $n-W+{\displaystyle \underset{i=1}{\overset{W-1}{}}}{}_i.$

$($c$)$ Show that if the edge weights are all distinct, there is a unique MST$.$

$2.($a$)$ Show how to implement the "contract" subroutine in $O(m)$ time. This algorithm takes as input a graph $G=(V,E)$ with some edges colored blue, and outputs a new graph $G^{\text{'}}=(V^{\text{'}},E^{\text{'}})$ in which vertices $v_{C}in{V}^{\text{'}}$ correspond to blue connected components $C$ in $G,$ there are no self$-$loops, and there is a $($single$)$ edge $e_C=(v_C,v_{C^{\text{'}}})$ if there exists some edge between the corresponding components $C,C^{\text{'}}$ in $G,$ and the weight of edge $(v_C,v_{C^{\text{'}}})$ is given by $mi{n}_{x,\text{y}\text{i}\text{n}\text{E}\text{:}\text{x}\text{i}\text{n}\text{C}\text{,}yin{C}^{\text{'}}}{w}_{xy}.$

$($b$)$ We proved in class that Boruvka reduces the number of nodes by a constant factor in each round, but what about the number of edges? Show an example of a graph with $n$ nodes and $m$ edges where the number of edges in $G_i$ remains $(m)$ for $(logn)$ rounds, even after cleaning up$.$

$($c$)$ Design an $O(mloglogn)-$time algorithm to find MST using algorithms$/$data$-$structures you have seen in the lectures.

$3.$ We will design yet another $O(mloglogn)-$time MST algorithm, but without using any fancy data$-$structures: in Boruvka's algorithm we scan all the edges in the graph in each pass, and we should avoid this repetition. Assume that $G$ is a connected simple graph, and edge weights are distinct.

$($a$)$ Suppose for each vertex, the edges adjacent to that vertex are stored in increasing order of weights. Show a slight variant of Boruvka's algorithm with runtime $O(m+nlogn).$

$($b$)(k-$partial sorting$)$ Given a parameter $k$ and a list of $N$ numbers, give an $O(Nlogk)-$time algorithm that partitions this list into $k$ groups $g_1,g_2,$cdots,$g_k$ each of size at most $|$~$\frac{N}{k}$~$|,$ so that all elements in $g_i$ are smaller than those in $g_{i+1},$ for each $i.$

$($c$)$ Adapt your algorithm from part $($a$)$ to handle the case where the edges adjacent to each vertex are not completely sorted but only $k-$partially$-$sorted. Ideally, your run$-$time should be $O(m+\frac{m}{k}logn+nlogn).$

$($d$)$ Use the two parts above $($setting $k=logn),$ preceded by some additional rounds of Boruvka, to give an $O(mloglogn)-$time MST algorithm.

$4.$ Recall that Dijkstra's algorithm computes the single$-$source shortest$-$path $($SSSP$)$ correctly for directed graphs with non$-$negative edge$-$lengths. For graphs with negative$-$length edges, we use typically the Bellman$-$Ford or Floyd$-$Warshall algorithms. Let us explore what happens if we use Dijkstra's algorithm instead. Assume that the graph does not have negative$-$length cycles.

$($a$)$ Show an example of a graph with negative edge$-$lengths where Dijkstra's algorithm returns the wrong shortest$-$path distance from the source $s.$ For your reference, we give Dijkstra's algorithm in algorithm $1.$

$1$ unmark all nodes while not all vertices marked do $\backslash ($ u $\backslash$leftarrow $\backslash )$ unmarked vertex with least label $\backslash ($ D$($u$)\backslash )$ mark $\backslash ($ u $\backslash )$ for all $,$ give a solution by giving examples and by making graph mathematically in depth