UC Berkeley—CS 170 Problem Set 7Lecturer: David Wagner Due on March 20 at 3:30 p.m.Problem Set 7 for CS 170FormattingPlease use the following format for the top of the solution you turn in, with one line peritem below (in the order shown below):<your username on cory.eecs><your full name>CS170, Spring 2003Homework #7Section <your section number>Partners: <your list of partners>(Remember to write your section number, not the name of your TA or the time of yoursection.) This will make it easier for us to sort and process your homeworks. Thank you!NoteWhen asked for an algorithm you must give (1) a brief informal description of the algorithm,(2) a precise description using pseudo-code, (3) an informal argument for termination andcorrectness of the algorithm, and (4) an analysis of the running time of the algorithm. Beclear about what the input to the algorithm is, how you measure the size of the input, andwhat constitutes a “step” in your running-time analysis.Problem 0. [Any questions?] (5 points)What’s the one thing you’d most like to see explained better in lecture or discussion sections?A one-line answer would be appreciated.(Sometimes we botch the description of some concept, leaving people confused. Some-times we omit things people would like to hear about. Sometimes the book is very confusingon some point. Here’s your chance to tell us what those things were.)Problem 1. [Union/Find] (20 points)Consider a variation of the Union/Find data structure, with the Union-by-rank heuristicbut without path compression. That is, we implement Makeset() and Union() as usual, butwe do not reset the parent pointers in Find().Show that there is some sequence of n calls to Makeset(), some number (at most n) ofcalls to Union(), and m calls to Find() that require Ω(m log n) work from this suboptimalimplementation.Problem set 7 due on March 20 at 3:30 p.m. 2Problem 2. [Most Likely Partition] (25 points)Let G = (V, E) be an undirected graph and p : E → [0, 1] be a weight function on the edges.G represents a communication network. For (u, v) ∈ E, p(u, v) is the probability that thelink between u and v fails on May 11, 2003. (May 11 is Mother’s Day—the busiest day ofthe year for the public phone network!) Assume that the links fail independently.We say that a set S ⊆ E of edges partitions G if its removal disconnects G (i.e., ifG0= (V, E \ S) is disconnected). If S ⊆ E, let p(S) be the probability that all edges in Sfail on Mother’s Day.(a) Let f(n) be the maximum number of partitions for a graph on n vertices. Is there someconstant c > 0 such that f(n) = O(nc)? Justify your answer informally.(b) We say that a set S ⊆ E that partitions G is a most likely partition for G if p(S) ismaximal among all sets that partition G. Give an O(n4) algorithm that computes amost likely partition for G.Your algorithm may have a small chance of providing an erroneous answer, as long asthe probability of erring is negligibly small.Problem 3. [How Biased Is the Coin?] (25 points)(a) You’re given a biased coin: it comes up heads with probability p and tails with prob-ability 1 − p. Describe a randomized algorithm to estimate p, in the sense that youralgorithm should output a guess for p that is in the range [p − 0.01, p + 0.01] withprobability at least 0.99.Hint: You could flip the coin many times and then try to estimate p from the numberof heads you’ve seen so far. How many times would you need to flip the coin to achievethe desired error bounds?Hint: If you’re not familiar with the variance of a random variable and Chebyshev’sbound, you might want to read up on that. Lectures 22 (Variance) and 23 (Polling andvoting) from CS 70 would be a good reference.(b) Now you’re given a communications network, i.e., an undirected graph G = (V, E)and a link failure probability function p : E → [0, 1], like in Problem 2. We wouldlike to determine the probability q that this network gets disconnected on Mother’sDay. Describe a randomized algorithm to estimate q in the sense given above (i.e.,you should output a guess so that at least 99% of the time your guess is in the range[q − 0.01, q + 0.01]).Warning: It turns out that computing q exactly is NP-hard, so don’t try to do that.Just try to estimate it.Problem 4. [A Faster Min-Cut] (25 points)The randomized algorithm for min-cut that we gave in class ran in O(n4) time. In thisproblem, we will develop another min-cut algorithm that is based on the same ideas buthas better asymptotic running time.Problem set 7 due on March 20 at 3:30 p.m. 3Consider the following algorithm:F(G):1: do |V |/2 times:2: pick (u, v) ∈ E with probabilityproportional to wt(u, v)3: contract (u, v), updating V and E4: return Trial(G)Trial(G):1: if |V | < 16:2: use the O(n4) algorithm given in class3: else:4: for i := 1, 2, 3, 4:5: Ci:= F(G)6: return the Ciof least weight(a) Write a recurrence relation for the worst-case running time of Trial in terms of n,where n = |V |.(b) Solve your recurrence relation from (a) to get the asymptotic worst-case running timeof Trial. Use Θ() notation.(c) Let C be a min-cut of G = (V, E). Consider the probability that steps 1–3 of F(G) neverdo a contraction on an edge crossing between C and V \ C. Show that this probabilityis at leastn−24n−4.(d) Let p(n) denote the probability that Trial(G) finds the min-cut of G with n vertices.Show how to derive this recurrence relation:p(n) ≥ 1 −1 −n − 24n − 4· p(n/2)4.(e) It turns out that the solution to the recurrence relation in (d) is p(n) = Ω(1lg n). (Youdo not need to show this!)Using this fact, describe an efficient algorithm that returns a min-cut of G with proba-bility at least 1 −12100. What is its running