Algorithm Design Techniques
Due: January 24, 2003 5pm
Last update: January 15, 2003
are to be left in the box near the labs, McConnell 1st floor.
Late assignments -10% per day, including weekends.
If you work closely with someone else, indicate the person's name(s) on
The final write-up of each assignment must, however, be your own work.
1. Read the course notes on selection and do all the exercises.
2. You are given a graph G=(V,E) and a set of positive
weights assigned to each edge. You are also given a spanning
tree T for G. Your job is either to verify that T is in fact a minimum weight
spanning tree, or give a tree T' that has strictly smaller weight than T.
Find an efficient algorithm for this problem, prove it is correct, discuss
how to implement it,
and give its worst case time complexity. Assume that the graph is
given by its adjacency matrix. Write your algorithm out in pseudo code.
Note: I am not asking you to find a minimum weight spanning tree, just
to verify whether or not a given tree is a minimum weight spanning tree.