Algorithm Design Techniques
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
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
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
2. (Stable Matching). Text, P. 24
3. (Truck scheduling) Text, P. 189, problem 3.
4. (Triatholon scheduling) Text,
P.191, problem 6.