Greedy algorithms, MST and ho man coding Assignment #4 Solution

Description

This set of questions focuses on:

greedy algorithms, MST and ho man coding

the proof techniques for proving the optimality of the greedy algorithm (arguing that greedy stay ahead). The exchange argument. Proof by contradiction.

1. Prove (by contradiction) that if the weights of the edges of G are unique then there is a unique MST of G. Also, show that the converse is not true by giving a counterexample.

2. The following statements may or may not be correct. In each case, either prove it (if it is correct) or give a counterexample (if it isn’t correct). Always assume that the graph G = (V ; E) is undirected. Do not assume that edge weights are distinct unless this is speci cally stated. Note that lightest = cheapest, heaviest = most expensive.

a. If graph G has more than jV j 1 edges, and there is a unique heaviest edge, then this edge cannot be part of a minimum spanning tree.

b. If G has a cycle that has a unique heaviest edge e, then e cannot be part of any MST.

c. Let e be any edge of minimum weight in G. Then e must be part of some MST.

d. If the lightest edge in a graph is unique, then it must be part of every MST.

3. Textbook 5.14

4. Textbook 5.15

5. Given a set of points fx1 x2 ::: xng on the real line. The goal is to use a smallest set of unit-length

closed intervals to cover all of the points. For example, for inputs f0:5 1:4 1:55 1:6 2:5g. An optimal

solution contains two intervals [0:45; 1:45] and [1:55; 2:55]. The rst interval covers the rst two points, whereas the remaining points are covered by the second interval. Consider the following greedy algorithm.

The greedy algorithm simply works by starting the rst interval at x1. It then removes all the points in [x1; x1 + 1], then repeat this process on the remaining points.

For example input f0:5 1:4 1:55 1:6 2:5g, the rst interval will be [0:5; 1:5]. We then skip the second
the point and start a new interval at the third point [1:55; 2:55].

Suppose our greedy algorithm output a solution with p unit-length closed intervals: I1; I2; :::; Ip, ordered on the real line. Consider an optimal solution J1; J2; :::; Jq ordered on the real line.

Prove that our algorithm stays ahead. That is, for 1 k min(p; q), our rst k intervals covers at least as many points as covered the J1; J2; :::; Jk. (Hint: use induction)

Prove that our solution is optimal building on the stay-ahead lemma.

1