Algorithm Design Techniques - assignment 1 COMP-360B

Algorithm Design Techniques Winter 2008

COMP-360 Assignment 1 Due: Beginning of class, Tues Jan 22

Late assignments -10% per day, including weekends.
Please give late assignments to Anil (T.A) in McConnell 337
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. (Stable Matching). Text, P. 22 problem 3.

2. (Greedy) Text, P. 193, problem 12.

3. (Greedy) Text, P.202-3, problems 27,28. (Hint: Use solution of 27 to solve 28).
______________________________________________________________________________________________________________________________

Note: You must prove the correctness of your algorithms, and analyze their running times.
Carefully review the proofs of similar results in the text first!