1 Minimum spanning tree Do problem 4.9 on page 192 of the textbook. For your convenience, here is the problem. Let G = (V; E) be a connected (undirected) graph with n vertices, m edges and positive edge costs (assume edge costs are distinct). Let T = (V; E0) be a spanning tree of G. The bottleneck edge of T is the edge of T with the greatest cost. A spanning tree T of G is called a minimum bottleneck spanning tree where there exists no spanning tree of G with a cheaper bottleneck edge. Questions: (a) Is every minimum bottleneck tree of G a minimum spanning tree of G? Prove or give a counter-example. (b) Is every minimum spanning tree of G a minimum bottleneck tree of G? Prove or give a counter-example. 2 MST Let G be a connected, undirected graph, where the edge weights are all distinct. You are also given a specific edge e in G. You want to find out whether e is contained in some minimum spanning tree. 1. First prove that e = (u; v) does not belong to any MST iff there is a path between u and v with edges all cheaper than e. 2. Give an O(jV j + jEj) algorithm for this problem. 3 Divide and conquer algorithm You are given a rooted tree T with n nodes. The tree may not be binary. You want to find the depth of T. Here, we define the depth of a node v in the tree to be the maximum number of nodes along a path from v to a leaf under v (going downwards). The depth of T is the depth of the root of T. Now give a divide and conquer algorithm for finding the depth of a tree. You need to analyze its running time. 4 Recurrence Solve the following recurrence. Show the steps. 1. T(n) = (12 1; T(n=4) + n1:5; if otherwise x ≥ 4 2. T(n) = (T1;(pn) + logn; if otherwise x ≥ 4 3. T(n) = T(n=2) + Θ(1), which is the running time of the binary search.
