Algorithm Design Techniques Winter
Due: Beginning of class, Tues Jan 22
Late assignments -10% per
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
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!