Algorithms

Question 1 (40 POINTS): Assume a reversed implementation of the Kruskal's Algorithm is introduced to find an MST, where T is initialized to be the set of all edges E of a graph G and all edges are sorted in decreasing order. When traversing each edge, the reversed Kruskal's Algorithm deletes an edge from T if it forms a cycle. If we assume all edge costs are distinct, does the reversed Kruskal's Algorithm compute an MST? Please discuss and justify your answer in detail on an example graph you give. Question 2 (40 POINTS): A Minimum Spanning Tree (MST) is defined for a connected, undirected and weighted graph Suppose we have a connected undirected graph whose weights are positive for some edges, and negative for some others 2.A) (20 POINTS) Does Kruskal's Algorithm run correctly on such a graph? Please work on an example graph and justify your answer. 2.B.) (20 POINTS) Does Prim's Algorithm run correctly on such a graph? Please work on an example graph and justify your