Below is Kruskal's algorithm exactly as it appears in the course notes.

1  function KRUSKAL(G = (V, E))
2     sort(E, key((u, v)) = w(u, v))
3     forest = UnionFind.initialise(n)
4     T = (V, {})
5     for each edge (u, v) in E do
6        if forest.FIND(u) != forest.FIND(v) then
7           forest.UNION(u, v)
8           T.add_edge(u, v)
9     return T

It is run with slow union. Assume the following costs, and that every other line takes constant time:

The edge list is supplied to the algorithm already sorted by weight, so line 2 has nothing left to do; that is why it costs \Theta(1).

Assume the graph is connected and simple, which implies |V| - 1 \le |E| \le |V|^2.

Give the worst-case time complexity of the whole algorithm, and explain how you got it. A complete answer states the cost of each part, adds them up, and then says which term dominates and why. No space complexity is needed.

Since you cannot type \Theta(), please write theta() in your answer.

A research group has a grant of exactly B dollars of compute credit, which must be spent down to zero. There are n machine types. Renting a machine of type i for one hour costs c_i > 0 dollars and completes j_i > 0 jobs. Any type may be rented any number of times. Maximise the jobs completed.

We solve this by defining the subproblem

maxJobs[x] = the most jobs completable by spending exactly x dollars

For example, with c = [3, 4], j = [5, 7] and B = 10, the best is one of each type plus one more of type 1, for 17 jobs.

Write the recurrence relation for this subproblem. Your answer must give:

• the base case or cases;
• an infeasible case, because some budgets cannot be met exactly;
• the general case, including the condition under which it applies;
• one sentence saying, in words, what the subproblem means.

You do not need to give pseudocode, prove anything, or state a complexity. Write mathematics however is easiest to type; max, <= and -infinity are all fine.

Consider the undirected graph below and Kruskal's algorithm for computing a minimum spanning tree. In which order are the edges added to the solution?

Consider the undirected graph below and Prim's algorithm for computing a minimum spanning tree using node S as the source node. In which order are the edges added to the solution?

You are running the Kruskal's algorithm to obtain the minimum spanning tree of a connected, undirected, weighted graph with 10 vertices (ID-0 to ID-9). Given the following parent array state of the union-find data structure during the algorithm's run, which of the following statement(s) is true?

You are running the Kruskal's algorithm to obtain the minimum spanning tree of a connected, undirected, weighted graph with 10 vertices (ID-0 to ID-9). Given the following parent array state of the union-find data structure during the algorithm's run, which of the following statement(s) is true?