Homework 5

15-212 Java, Spring 1998

Assigned March 18, 1998
Due April 1, 1998 
Instructors: Mosur and Tygar


This assignment is due at start of your section on April 1. Please read the class policies for collaboration, cheating, and late assignments. Answers that are unclear, illegible, rambling, or otherwise difficult to understand will receive no credit. The best answer is the shortest correct answer.

 

IMPORTANT: Same as always. Put your name, your section, and your email at the top of the first page of each part.

 


Part I: Slow Problems

1. Solve the traveling salesman problem for five cities A, B, C, D, and E with the following distance matrix: (L&P 6.2.3)
 
 
B C D E
A 8 4 5 9
B 1 7 3
C 6 2
D 5
 

2. Does the undirected graph on L&P page 288 have a Hamilton cycle? What is the largest clique, largest independent set, and smallest node cover of this graph? (L&P 6.2.5)
 
 
 

Part II: It's All the Same to Me

1. Show that the Hamilton Path problem is NP-complete by reducing the Hamilton Cycle problem to it. (L&P 7.3.3 part a1)
 
 
 

Part III: Wishful Thinking

1. Show that the Traveling Salesman Problem remains NP-complete even if the distances are required to obey the triangle inequality. (Hint: Look back at the original proof that the Traveling Salesman Problem is NP-complete.)  (L&P 7.4.3)
 

 END OF ASSIGNMENT 5