$1.$ Given the following edge$-$weighted graph:

$615$

$0-11\mathrm{.}3$

$0-25\mathrm{.}2$

$0-32\mathrm{.}1$

$0-46\mathrm{.}8$

$0-53\mathrm{.}5$

$1-25\mathrm{.}6$

$1-32\mathrm{.}0$

$1-46\mathrm{.}9$

$1-53\mathrm{.}6$

$2-35\mathrm{.}7$

$2-46\mathrm{.}1$

$2-56\mathrm{.}0$

$3-47\mathrm{.}0$

$3-55\mathrm{.}1$

$4-57\mathrm{.}8$

a$)$ Show a trace of the execution of Kruskal's Algorithm on this graph. Your trace should be in the style of the trace shown on page $624$ of the text. $[5]$

b$)$ How many elements are inserted into the priority queue used by Kruskal's algorithm when computing the MST for this graph? $[1]$

c$)$ How many elements of the priority queue do you consume before the algorithm completes computing the MST$?[1]$

d$)$ Show a trace of the execution of the eager version of Prim's Algorithm on this graph. Your trace should be in the style of the trace shown on page $621$ of the text. $[5]$

e$)$ As Prim's algorithm executes, how many elements of each of the edgeTo$[]$ and distTo$[]$ arrays must be updated each time an edge is added to the MST$?[1]$

e$)$ Which of the two algorithms is a better choice for computing the MST for this graph? Why? $[2]$

$2.$ Given the following edge$-$weighted graph:

$68$

$0-14\mathrm{.}1$

$0-24\mathrm{.}5$

$1-22\mathrm{.}1$

$2-33\mathrm{.}5$

$2-44\mathrm{.}8$

$2-52\mathrm{.}4$

$3-43\mathrm{.}9$

$4-53\mathrm{.}7$

a$)$ Show a trace of the execution of Kruskal's Algorithm on this graph. Your trace should be in the style of the trace shown on page $624$ of the text. $[5]$

b$)$ How many elements are inserted into the priority queue used by Kruskal's algorithm when computing the MST for this graph? $[1]$

c$)$ How many elements of the priority queue do you consume before the algorithm completes computing the MST$?[1]$

d$)$ Show a trace of the execution of the eager version of Prim's Algorithm on this graph. Your trace should be in the style of the trace shown on page $621$ of the text. $[5]$

e$)$ Contrast the amount of work Prim's algorithm has to do for this graph and the graph in the previous question when updating the edgeTo and distTo arrays. $[1]$

f$)$ Which of the two algorithms is a better choice for computing the MST for this graph? Why? $[2]$