CMSC 435 Algorithm Analysis & Design

Answers to Homework # 5

1. Let G be an arbitrary connected, undirected graph with a distinct cost c(e) on every edge. Suppose that e^*is the cheapest edge in G; that is c(e^*) £ c(e) for every edge e ¹ e^*. Then there is a MST, T, of G that contains the edge e^*.

True. Suppose there is a MST, T', that does not contain e^*. Assume e^* is the edge

connecting vertices u and v. If we add e^* to T' we create a cycle. We can remove

the cycle and get a new tree T by removing the larger edge (t,u) or (v, w) that are

found in T'. Since c(T) = c(T') - c((v, w)) + c(e^*), and c((v, w)) > c(e^*), we have

c(T) < c(T') for any T' that does not include e^* and any MST must include e^*.

2. G is a graph in which all edge costs are positive and distinct. Let T be an MST on G. Suppose we square all of the edge costs.

a) T is still a MST for the new edge costs. True. Run Kruskal's algorithm. The edges will still be sorted in the same order and the algorithm will put the same subset of edges into the MST.

b) Let P be the minimum-cost path between vertices s and t in the graph with the original edge weights. The P is still the minimum cost path between s and t after the edge weights have all been squared. False. Consider a graph with vertices s, u, t and edges (s, u) with cost 3, (u, t) with cost 3, and (s, t) with cost 5. The min-cost s-t path is P = {(s, t)} with cost 5. If all of the edges are squared, the min-cost path, P' is P' = {(s, u), (u, t)} with cost 18.

3. Prove that greedy approach is optimal given the constraints on ordering packages. Use induction. Let b_i be the last box delivered (or en route) in the greedy approach and b_j the last box in the alternative approach.

Base case: In the greedy approach the first truck is filled to the point where it cannot hold the next package. The

greedy truck holds boxes b₁…,b_i and the other truck holds boxes b₁…,b_j where j £ i.

The Inductive hypothesis: Assume the hypothesis holds for the first k - 1 trucks. i' is the number of boxes

delivered by the first k - 1 trucks in the greedy approach and j' by the other approach and j' £ i'. The k^th truck

filled by the alternative approach will hold boxes b_j'+1,…,b_j. The greedy truck can hold boxes b_i'+1,…,b_j,

and, since j' £ i', it can potentially still hold more boxes. This proves the claim of the optimality of the greedy

filling method.

4. The greedy sequence matching algorithm to find a subsequence S', if any, in a sequence S. Let S consist of the sequence s₁, s₂, …, s_n and S' the sequence s'₁, s'₂, …, s'_m. Let k_i denote the position of the i^th match between the two substrings. The algorithm below finds the first occurrence, if any, of the match, or returns the result that no match exists.

Initialize i = 1 (index over S) and j = 1 (index over S')

While i <= n and j <= m

If s_i is the same as s'_j

let k_j = i

let i = i + 1 and j = j + 1

Else

let i = i + 1

EndWhile

If j = m + 1 return the result subsequnce found at indicies: k₁, …, k_m

Else return that S' not in S

Algorithm runs in O(n)

5. (Chapter 4 # 7) Possible greedy orderings are by decreasing finishing times on the supercomputer, decreasing finishing times on a PC, or decreasing sum of finishing times on the supercomputer and PC. Let G be the schedule where we run jobs on the supercomputer in the order of decreasing finishing time on the PC. Let job J_j be the job that finishes last on the PC in the greedy algorithm's schedule G, and let S_j be the time that this job finishes on the supercomputer. The overall finish time for this job is therefore S_j + f_j. In any other schedule, one of the first j jobs, in the order specified by G, must finish on the supercomputer at some time T >= S_j (as the first j jobs give exactly S_j amount of work to the supercomputer). Let that job be J_i. Now job J_i needs PC time at least as much as job j (due to the ordering of G), and so it finishes at time T + f_i >= S_j + f_j. So this schedule is, at best, no better than G.

6. (Chapter 4 # 8) Suppose by way of contradiction that T and T' are two distinct MSTs of G. Since T and T' have the same number of edges but are not equal, there must be some edge e' in T' that is not in T. If we add e' to T we get a cycle. Let e be the most expensive edge in this cycle. Then by the Cycle Property, e does not belong to any MST of G, contradicting the fact that it is in at least one of T, T'.

7. (Chapter 4 # 9) We define a minimum-bottleneck spanning tree of a graph G to be a tree T such that there is no tree T' with a cheaper bottleneck edge.

a) Is every minimum-bottleneck tree of G a MST of G? No!

Consider a tree with vertices {v₁, v₂, v₃, v₄} with edges between each pair of

vertices and a weight from v_i to v_j of i + j. Then every tree has a bottleneck edge of

weight at least 5, so the tree with a path through vertices v₃, v₂, v₁, v₄ is a

minimum-bottleneck tree. It is not a MST, since the tree with edges from v₁ to every

other vertex will have lower total cost (cost of first tree = 5 + 3 + 5 = 13, cost of

tree with all edges from v₁ = 3 + 4 + 5 = 12)

a) Is every MST of G a minimum-bottleneck tree of G? True. Suppose that T is a MST of G and T' is a spanning tree with cheaper bottleneck edge. Thus T contains an edge e that is heavier than every edge in T'. If we add e to T' it forms a cycle on which it is the heaviest edge. By the Cut Property, then, e does not belong to any MST, contradicting the fact that it is in T and T is a MST.