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.
______________________________________________________________________________________________________________________________