## Algorithm Design Techniques

COMP-360              Assignment 1              Due: Sep 25, 2006 noon

Late assignments  -10% per day, including weekends. Put assignments in the box, McConnell 1st floor.
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. (Greedy Selection)  Read the course notes on selection .
( http://www.cs.mcgill.ca/~avis/courses/360/notes/selection.pdf )

(a) Consider a selection problem for which there is an instance for which P1 and P2 hold but P3 fails.
Show how to assign a weight function so that the greedy selection algorithm fails.
Give an example of a selection problem of this type.

(b) Suppose you have a selection problem satisfying P1, P2, and P3, and suppose all the weights are different.
Prove that there is a unique optimum solution to the greedy selection problem.

2. (Stable Matching). Text, P. 24 problem 5.

3. (Truck scheduling) Text, P. 189, problem 3.

4. (Triatholon scheduling) Text, P.191, problem 6.
______________________________________________________________________________________________________________________________