The algorithm used in lecture was minimum spanning arborescence.

5. (a) Find a directed graph where Prims algorithm doesn't yield the arborescence of minimum cost. Your example graph should not contain more than 5 nodes. Note that, in a directed graph, node v is a neighbor of node u only if the directed edge (u, v) exists. Hint: A graph of 3 nodes would work. Answer: (b) For each given n > 3, find a complete graph of |V = n nodes where the algorithm introduced in the lecture finishes in O(El) time without collapsing any cycle to a super node. Hint: You can set certain edges to have very large weights. Answer: (c) For each given n > 3, find a complete graph of |V | = n nodes where the algorithm introduced in the lecture finishes in (V||El) time. The algorithm should collapse n 2 cycles to super nodes iteratively. Answer: (d) Propose a modification to the algorithm so that its running time becomes O( V12) on graphs you created in part (c). For simplicity, your new algorithm only needs to output the minimum cost of spanning arborescences. Answer: 5. (a) Find a directed graph where Prims algorithm doesn't yield the arborescence of minimum cost. Your example graph should not contain more than 5 nodes. Note that, in a directed graph, node v is a neighbor of node u only if the directed edge (u, v) exists. Hint: A graph of 3 nodes would work. Answer: (b) For each given n > 3, find a complete graph of |V = n nodes where the algorithm introduced in the lecture finishes in O(El) time without collapsing any cycle to a super node. Hint: You can set certain edges to have very large weights. Answer: (c) For each given n > 3, find a complete graph of |V | = n nodes where the algorithm introduced in the lecture finishes in (V||El) time. The algorithm should collapse n 2 cycles to super nodes iteratively. Answer: (d) Propose a modification to the algorithm so that its running time becomes O( V12) on graphs you created in part (c). For simplicity, your new algorithm only needs to output the minimum cost of spanning arborescences