Suppose that we have a sequence of MakeSet-Find-Union operations in which no Find appears before any Union. What is the computational time for this sequence?
(Question 24.1-5, Textbook, p. 655) Let G = (V,E) be a weighted directed graph. Develop an O(nm)-time algorithm that finds the value δ(v) for every vertex v, which is defined as:
δ(v) = min{the length of the shortest path in G from w to v}.
w∈V
3. Assume that multiple edges are allowed in a weigthed graph G, which is given in an adjacency list G[n]. Therefore, for each vertex v, the linked list G[v] for v may contain elements of the forms [u,w1] and [u,w2], standing for two edges from v to u, with weights w1 and w2, respectively. Now the goal is that for each pair of vertices in the graph G, we want to remove all multiple edges except the one with the largest weight. Design a linear-time algorithm for this problem.
4.Modify the QuickSort algorithm so that the pivot is selected using the linear-time MedianFinding algorithm. Prove that this modified QuickSort algorithm takes time O(nlogn) in the worst case. Discuss why this algorithm is not used in practice.
