Algorithm Design Techniques

COMP-360 Assignment 2 Due: October 10, 5pm

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. (Independent set in a path) Text, P. 312, problem 1.

2. (Office Location). Text, P.315, problem 4.

3. (PC shipping) First do: Text, P. 323, problem 11.
Then, compute the optimum solution (by hand or by computer) for r=1, c=10 and the sequence of values
10, 20, 5, 5, 13, 11, 8, 6, 9, 17, 5

4. (Verification of shortest paths) Text, P.331, problem 23(a).
______________________________________________________________________________________________________________________________