$30.00
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.

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.

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.


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.



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



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



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


Textbook 5.14

Textbook 5.15

Given a set of points fx_{1} x_{2} ::: x_{n}g on the real line. The goal is to use a smallest set of unitlength
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 x_{1}. It then removes all the points in [x_{1}; x_{1} + 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 unitlength closed intervals: I_{1}; I_{2}; :::; I_{p}, ordered on the real line. Consider an optimal solution J_{1}; J_{2}; :::; J_{q} 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 J_{1}; J_{2}; :::; J_{k}. (Hint: use induction)
Prove that our solution is optimal building on the stayahead lemma.
1