2. Suppose you are given a graph G with weighted edges, and your goal is to find a cut whose total weight (not just number of edges) is smallest. (a) Describe an algorithm to select a random edge of G, where the probability of choosing edge e is proportional to the weight of e (b) Prove that if you use the algorithm from part (a), instead of choosing edges uniformly at random, the probability that GuEssMiNCUT returns a minimum-weight cut is still 2(12) (c) What is the running time of your modified GUESSMINCuT algorithm? 2. Suppose you are given a graph G with weighted edges, and your goal is to find a cut whose total weight (not just number of edges) is smallest. (a) Describe an algorithm to select a random edge of G, where the probability of choosing edge e is proportional to the weight of e (b) Prove that if you use the algorithm from part (a), instead of choosing edges uniformly at random, the probability that GuEssMiNCUT returns a minimum-weight cut is still 2(12) (c) What is the running time of your modified GUESSMINCuT algorithm