CSE 417 Assignment #3
Winter 2001

Due: Monday, February 12, 2001.

1. Skiena's book, page 111, Problem 4-5.

2. Skiena's book, page 111, Problem 4-8.

3. Skiena's book, page 112, Problem 4-13.

4. Skiena's book, page 112, Problem 4-14.

5. Skiena's book, page 112, Problem 4-12.

6. (Bonus) Modify your solution to 4-12 to also handle the case when edge weights might be negative. (If there is a negative weight cycle then the minimum weight is -infinity because one can go around that cycle an arbitrary number of times.) Analyze your algorithm's run time.

7. (Bonus) A bottleneck minimum spanning sub-graph, B, of a graph G is a spanning sub-graph of G (i.e., any two vertices connected in G are also connected in B) that has its largest weight edge as small as possible. (There might be more than one such sub-graph.) Describe how one can efficiently find a bottleneck minimum spanning sub-graph and analyze your algorithm's running time.