May 11, 2010
Douglas Holmes
COMP510
Spring 2011
Assignment 7

23.1-1) Let (u, v) be a minimum-weight edge in a graph G. Show that (u, v) belongs to some minimum spanning tree of G.

If G is a minimum spanning tree, and A is a subset of the edges in G, then we would find that certain lighter edges would be added to A. Since these edges would be connected to (u,v), it can be asserted that (u,v) is safe for A. Since it is safe for A, it can be used in creating a minimum spanning tree in G.

23.1-6) Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. Show that the converse is not true by giving a counterexample.

The graph has a unique minimum spanning tree in this case because every cut produces a unique light edge, making all the edges in the spanning tree unique, which would give us our unique minimum spanning tree. The converse would be incorrect, because there might be cuts with equal minimum weights, but still allowing for a minimum spanning tree. An example of this would be the tree (A)- 1 -(B)- 1 -(C), which has duplicate weights while still being a minimum spanning tree.

23.2-1) Kruskal's algorithm can return different spanning trees for the same input graph G, depending on how ties are broken when the edges are sorted into order. Show that for each minimum spanning tree T of G, there is a way to sort the edges of G in Kruskal's algorithm so that the algorithm returns T.

By sorting the edges of the graph in ascending order and breaking the ties top down, we would eventually arrive at the desired minimum spanning tree.

23.2-2) Suppose that the graph G = (V, E) is represented as an adjacency matrix. Give a simple implementation of Prim's algorithm for this case that runs in O(V²) time.

Prim's algorithm would work in O(V²) time by altering the algorithm to sort through V twice. At line 8, instead of using an adjacency list, we would just have to loop from 1 to V, just like the first line of the algorithm.

24.1-1) Run the Bellman-Ford algorithm on the directed graph of Figure 24.4, using vertex z as the source. In each pass, relax edges in the same order as in the figure, and show the d and π values after each pass. Now, change the weight of edge (z, x) to 4 and run the algorithm again, using s as the source.

First, the Bellman-Ford run:

	s	t	x	y	z
d	2	5	6	9	0
π	z	s	z	s	Ø

Using s as the source:

	s	t	x	y	z
d	0	2	4	7	-2
π	Ø	x	z	s	t

Since the graph has a negative weight cycle reachable from s, this graph does not have a shortest path solution using Bellman-Ford from source s.

24.1-3) Given a weighted, directed graph G = (V, E) with no negative-weight cycles, let m be the maximum over all pairs of vertices u, v ␣ V of the minimum number of edges in a shortest path from u to v. (Here, the shortest path is by weight, not the number of edges.) Suggest a simple change to the Bellman-Ford algorithm that allows it to terminate in m + 1 passes.

With m representing the maximum over all pairs of vertices, we'll have the shortest path weight for every vertex by the time the algorithm reaches that many iterations. Since we don't know m off the bat, the simple solution would be to check for changes. If everything is the same, the algorithm is done.

For this, we would implement the following modification of Bellman-Ford:
INITIALIZE-SINGLE-SOURCE(G, s)
changes = TRUE
while changes == TRUE
changes = FALSE
for each (u, v) in E[G]
RELAX(u,v,w)
end
end

We would also need to make a change to RELAX:
if d[v] > d[u] + w(u, v)
d[v] = d[u] + w(u, v)
π[v] = u
end
changes = TRUE

24.2) A d-dimensional box with dimensions (x1, x2,..., xd) nests within another box with dimensions (y1, y2,..., yd) if there exists a permutation π on {1, 2,..., d} such that xπ(1) < y1, xπ(2) < y2,..., xπ(d) < yd.
a. Argue that the nesting relation is transitive.
b. Describe an efficient method to determine whether or not one d-dimensional box nests inside another.
c. Suppose that you are given a set of n d-dimensional boxes {B1, B2,..., Bn}. Describe an efficient algorithm to determine the longest sequence of boxes such that Bi(j) nests within Bi(j+1) for j = 1, 2,..., k - 1. Express the running time of your algorithm in terms of n and d.

For a, let X nest within Y, and Y nest within Z with dimensions (z1, z2,..., zd). From here, we can construct a permutation where xπ(1) < y1, xπ(2) < y2, ... xπ(d) < yd, and the same with y and z, therefore the same can be said for x and z, making the nesting relation transitive.
For b, let us assume that each box is ordered such that xπ(1) < xπ(2) < ... < xπ(d). From this, compare the boxes for each member. If xi < yi for i=1 to d, then X nests within Y.
For c, we must order the dimensions of Bi(j) where i = 1 to d, then compare to Bi(j+1) using the method from B. Then we can use the longest increasing subsequence to sort the dimensions of Bi(j+1) from 1 to d, and run the same nesting check. From here, we take the longest sequence of nesting boxes determined by the checks and return it. This algorithm has a run time of O(dn² + dn * ln(d)).

References:

Course Textbook: T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, Second Edition.
Course Textbook: T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, Third Edition.
For question 24.1-3: http://csuci.mathworld.info/29.html