Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________
Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Problem 0 (assessment: self_______ final_______)



                        Path X:  a   b   c   e   d      weight: 19
	                         0   1   2   3   4 

	Path after 2-OPT (0,1):  b   a   c   e   d      weight: 18

  
        Path after 2-OPT (0,2) applied to original X: ______________________  weight:___________________

  
        Path after 2-OPT (0,3) applied to original X: ______________________  weight:___________________

  
        Path after 2-OPT (1,2) applied to original X: ______________________  weight:___________________

  
        Path after 2-OPT (1,3) applied to original X: ______________________  weight:___________________

  
        Path after 2-OPT (1,4) applied to original X: ______________________  weight:___________________

  
        Path after 2-OPT (2,3) applied to original X: ______________________  weight:___________________

  
        Path after 2-OPT (2,4) applied to original X: ______________________  weight:___________________

  
        Path after 2-OPT (3,4) applied to original X: ______________________  weight:___________________

Problem 1 (assessment: self_______ final_______)

Let X[0], X[1], ..., X[n-1] be your current cycle. And let E[u,v] be the weight of the edge between vertices u and v. Finally, let w be the weight of the current cycle. Come up with a formula for the weight of the cycle that would result if you applied 2-OPT (i,j)? The formula should be in terms of w, X and E.