Deliverables: To complete this assignment you must --
1.) Perform the traveling salesman problem below, filling in the answers on a copy of this html page, and

Introduction: The Traveling Salesman Problem
In this problem, the nodes of the graph represent locations and the edges represent the cost (in money or time or distance) to travel from one location to another. The edges are represented by the nodes they connect. The salesman starts in node 1. Your job is to design a route of travel so that he visits every location exactly once and returns to node 1 while making his total trip a minimum cost.

Use the graph below. Your solution will be the route of least cost, presented as a list of nodes (ex: 1 - 4 - 2 - 5 - 6 - 7 - 3 - 1). Then answer the questions below.

1. Record the values assigned for each edge in your HTML file (the ones above are randomly generated in JavaScript each time the page is loaded. The grader cannot check your work unless you record them).
2. Decision problem: Can you find a route for the salesman with a cost less than 80? What is the route?
3. For question 2, what approach did you use? Was it easy to tell when you acheived a correct solution? Why?
4. Optimization Problem: What is the cost of the "cheapest" route possible for your salesman? What is the route?
5. For question 4, what approach did you use? Was it easy to tell when you acheived a correct solution? Why?
6. Assume one of your classmates gave you their optimized solution to the traveling salesman problem but not the values of the edges for the graph they used. Could you verify their solution was correct? Why or why not?
7. Assume they gave you their solution to a sorting problem (ie a sorted list) without giving you the original unsorted list. Could you verify that they had performed the sort correctly (assume the solution and the original list contain the same numbers, just in different order)? Why or why not?