Problem 5: Evaluate [ 20 points] This problem is an extension of the algorithms in the programming assignment. As a recap, on the programming assignment, you are given a graph representation of brain interaction regions and asked to find a minimum spanning tree of this representation (that's the first part). In the second part, you are asked to find the geodesic diameter of the resulting tree, which ignores the weights on the edges in the tree and focuses instead on the structure of the conneotivity of the tree. The geodesic diameter is a metric that medical researchers have found to be important in indicating the possibility of various diseases. As a researcher, one might also wonder whether the weighted diameter, or the longest shortest cost path in a graph provides any information about various diseases or treatment. To investigate this, one would have to find weighted diameters on various networks inside a brain atlas and attempt to discover whether there is any correlation between the weighted diameter and diseases of interest. (a) Give an algorithm to compute the weighted diameter of the complete graph (not the minimum spanning tree). Your algorithm should be efficient (i.e., it's running time should be polynomial in the size of the graph representation). (b) Assuming the graph is dense, what implementation choices would you make (in terms of data structures to support your algorithm)? (c) Using the data structures you chose above, what is the running time of your algorithm? n...s. ae tisht of a bound as possible. (d) If you were to use the same algorithm to compute the weighted diameter of the minimum spanning tree you are creating in the programming assignment, how would your choices of data structures change? What is the resulting runtime of the algorithm on the tree (again, give as tight of a bound as possible)