Algorithm Design Techniques
COMP-360
Assignment 4
Due: Tues Dec 5, 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. (NP-completeness)
Text, P 506, problem 4.
2. (NP-completeness)
Text, P 507, problem 6.
3. (Approximation Algorithms) Text, P 652, problem 3.
4. (Approximation Algorithms) Text, P 653, problem 5.