Homework 9

Details

Do the following problems from the Algorithms textbook:

1. Exercise 8.2. Hint: You will probably run the Rudrata path algorithm multiple times in order to find the path. But what is going to be different about each time you run it? Be sure to give a complete and clear description of your algorithm and justify the fact that it is polynomial-time.
2. Exercise 8.10. Do any five of them. Clearly indicate which ones you are doing! Be clear about how the problem is a generalization of another NP-Complete problem.
3. Exercise 8.18. Do not over think this one, but do give enough details to make it clear.