Algorithm Design Techniques

COMP-360B Assignment 1 Due: January 24, 2003 5pm

Last update: January 15, 2003

Assignments 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 your homework.
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.
( http://www.cs.mcgill.ca/~avis/courses/360/notes/selection.ps )

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.