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(|V | + |E|) 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.
(12T (n/4) + n1.5, if x ≥ 4
1. T (n) =
2. T (n) =
1, otherwise
(T (√n) + logn, if x ≥ 4
1, otherwise
3. T (n) = T (n/2) + Θ(1), which is the running time of the binary search.
