CS 4349.002. Advanced Algorithm Design and Analysis Spring 2019 Assignment 8 Wed, Mar 27 Due: 11:59 PM, Sun, Apr 7. 1. Write an algorithm that tests if a graph G=(V,E) contains an MST that includes a given edge e=(u,v) in E. If such an MST exists, the algorithm returns it. If there is no MST of G that contains e, then it returns null. Signature: List mstWithGivenEdge( Graph g, Edge e=(u,v) ). Optional problems (extra credit): 2. Ex. 23.1-3 (p. 629) [Every MST edge is a light edge for some cut; write this proof without assuming that the given tree was computed using Prim/Kruskal/generic MST algorithms]. 3. Prove that the following claim is false by finding a counterexample: if e=(u,v) is an edge in an MST, and (S,V-S) is a cut crossed by e, then e is a light edge for this cut. 4. Ex. 23.1-11 (p. 630) [MST after decreasing weight of edge]. 5. Problem 23-4 (p. 641) [Alternative MST algorithms].