$1.($a$)$ For a graph G$,$ consider two edge$-$weight functions w$1$ and w$2$ such that

w$1($e$)$ w$1($e

$)$ w$2($e$)$ w$2($e

$)$

for all edges e$,$ e E$.$ 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,$ W$\},$ where W $2.$ Let Gi be the edges of weight

at most i$,$ and i be the number of components in Gi

$.$ Then show that the MST in G has weight exactly

n W $+$

PW$1$

i$=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 $=($V

$,$ E

$)$ in which vertices vC V

correspond to blue connected components C in G$,$ there are no self$-$loops, and there is a $($single$)$ edge

eC $=($vC $,$ vC $)$ if there exists some edge between the corresponding components C$,$ C

in G$,$ and the weight

of edge $($vC $,$ vC $)$ is given by min

x$,$yE:xC$,$yC

wxy$.$

$($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 Gi remains $($m$)$ for $($log n$)$ rounds, even after cleaning up$.$

$($c$)$ Design an O$($m log log n$)-$time algorithm to find MST using algorithms$/$data$-$structures you have seen in the

lectures.

$3.$ We will design yet another O$($m log log n$)-$time MST algorithm, but without using any fancy data$-$structures: in

Boruvkas 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 Boruvkas algorithm with runtime O$($m $+$ n log n$).$

$($b$)($k$-$partial sorting$)$ Given a parameter k and a list of N numbers, give an O$($N log k$)-$time algorithm that

partitions this list into k groups g$1,$ g$2,,$ gk each of size at most N$/$k$,$ so that all elements in gi are

smaller than those in gi$+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 $+$

m

k

log n $+$ n log n$).$

$($d$)$ Use the two parts above $($setting k $=$ log n$),$ preceded by some additional rounds of Boruvka, to give an

O$($m log log n$)-$time MST algorithm.

$4.$ Recall that Dijkstras 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 Dijkstras algorithm instead. Assume that

the graph does not have negative$-$length cycles.

$($a$)$ Show an example of a graph with negative edge$-$lengths where Dijkstras algorithm returns the wrong

shortest$-$path distance from the source s$.$ For your reference, we give Dijkstras algorithm in algorithm $1.$

$1$

Algorithm $1$: Dijkstras Algorithm

$1$ D$($s$)=0,$ D$($v$)=$ for all v $=$ s

$2$ run Dijkstra$-$Iteration

Algorithm $2$: Dijkstra$-$Iteration

$1$ unmark all nodes

$2$ while not all vertices marked do

$3$ u unmarked vertex with least label D$($u$)$

$4$ mark u

$5$ for all out$-$edges $($u$,$v$)$ of u do

$6$ D$($u$)$ min$\{$D$($v$),$ D$($u$)+$ l$($u$,$ v$)\}$

$7$ end

$8$ end

$($b$)$ Now suppose we iterate through Dijkstras algorithm K times $($shown formally as under$).$ Consider any

node v such that the shortest$-$path from s to node v contains at most K $1$ negative$-$length edges. Show

that the final value of the label D$($v$)$ equals the length of this shortest s$-$v path.

Algorithm $3$: K$-$Fold Dijkstras Algorithm

$1$ D$($s$)=0,$ D$($v$)=$ for all v $=$ s

$2$ for i $=1,2,,$ K do

$3$ run Dijkstra$-$Iteration

$4$ end