# CSE 417 Assignment #3

Winter 2001

### Due: Monday, February 12, 2001.

- Skiena's book, page 111, Problem 4-5.
- Skiena's book, page 111, Problem 4-8.
- Skiena's book, page 112, Problem 4-13.
- Skiena's book, page 112, Problem 4-14.
- Skiena's book, page 112, Problem 4-12.
- (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.
- (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.