Assignment 5 due by the end of class Wednesday February 28 2001.
  1. Show that for all n there are inputs for which the running time of the simple implementation of P/D MST is bounded below by a constant times n cubed. Hint: complete the argument made in the lecture.
  2. Prove that the operation "decrease-key" can be performed in log n time in a heap with n keys.
  3. The straightforward implementation of Prim's MST algorithm takes Theta(n^3) time; storing only the best edge for each fringe vertex takes Theta(n^2) time. [See my fall 2000 204 notes, week 9 page 7.] Suppose that the values of "best edge for each fringe vertex" are stored in a priority queue implemented with a heap, instead of in an array. Explain in detail how this leads to a running time of O(n+mlog(n)).
  4. It is known that if no two edges of a weighted graph have the same weight, then the graph has a unique minimum spanning tree (e.g. see Baase). Prove or disprove the two following statements.
    1. If a weighted graph has an MST in which all edge weights are distinct, then that is the only MST of that weighted graph.
    2. Let x be the maximum weight of an edge of an MST T of a weighted graph G, and suppose that in G, for every possible weight at most x, there is at most one edge with that weight. Then T is the only mst of G.