1. Let graph G have the six vertices a,b,c,d,e, and f, and the nine edges
    ac with weight 15
    ad with weight 10
    ae with weight 1
    bc with weight 3
    bd with weight 20
    be with weight 5
    fc with weight 12
    fd with weight 7
    fe with weight 9

(a) What is the minimum spanning tree of this graph?

(b) In what order would the Prim-Dijkstra-Jarnik algorithm, starting
from vertex a, add edges to form the MST?

(c) In what order would Boruvka's algorithm add edges to form the MST?

(d) In what order would Kruskal's algorithm add edges to form the MST?


2. The following pseudocode for performing a find operation in the
union-find data structure does not correctly implement the data
structure. Explain what is wrong with it.

def find(x):
    y = x
    while y is not a root:
        y = parent(y)
    parent(x) = y
    return y

3. What is the running time for each of the three algorithms,
Prim-Dijkstra-Jarnik, Boruvka, and Kruskal, when used to build a maze
from a k-by-k grid of squares? For Prim-Dijkstra-Jarnik, use the
analysis for the variant of the algorithm that uses binary heaps, and
for Kruskal's algorithm, assume that the sorting stage of the algorithm
is done using a comparison sorting algorithm.  Express your answers in
O-notation, as a function of k.