Home Chapter6: Quiz #1

# Quiz #1

This activity contains 15 questions.

## The number of Hamilton circuits in is

 15 14! 15! None of the above

Questions 2 to 5 refer to the following situation: A delivery truck must deliver furniture to 4 different locations (A, B, C, and D). The trip must start and end at A. The graph below shows the distances between locations (in miles). We want to minimize the total distance traveled.

The nearest neighbor algorithm applied to the graph yields the following solution:

 A, C, B, D, A. A, B, D, C, A. A, D, C, B, A. A, D, B, C, A. None of the above

## The cheapest link algorithm applied to the graph yields the following solution:

 A, D, B, C, A. A, B, D, C, A. A, D, C, B, A. A, C, B, D, A. None of the above

## The repetitive nearest neighbor algorithm applied to the graph yields the following solution:

 A, B, D, C, A. A, D, C, B, A. A, D, B, C, A. A, C, B, D, A. None of the above

## An optimal solution to this problem is given by

 A, D, C, B, A. A, C, D, B, A. A, B, D, C, A. A, C, B, D, A. None of the above

Questions 6 to 9 refer to the following situation: A traveling salesman’s territory consists of the 5 cities shown on the following mileage chart. The salesman must organize a round trip that starts and ends at Louisville (his hometown) and will pass through each of the other four cities exactly once.

The nearest neighbor algorithm applied to this problem yields the following solution:

 Louisville, Chicago, Buffalo, Boston, Columbus, Louisville. Louisville, Columbus, Buffalo, Boston, Chicago, Louisville. Louisville, Boston, Buffalo, Chicago, Columbus, Louisville. Louisville, Columbus, Chicago, Buffalo, Boston, Louisville. None of the above

## The cheapest link algorithm applied to this problem yields the following solution:

 Louisville, Columbus, Buffalo, Boston, Chicago, Louisville. Louisville, Columbus, Chicago, Buffalo, Boston, Louisville. Louisville, Boston, Buffalo, Chicago, Columbus, Louisville. Louisville, Chicago, Buffalo, Boston, Columbus, Louisville. None of the above

## The repetitive nearest neighbor algorithm applied to this problem yields the following solution:

 Louisville, Columbus, Buffalo, Boston, Chicago, Louisville. Louisville, Columbus, Chicago, Buffalo, Boston, Louisville. Louisville, Boston, Buffalo, Chicago, Columbus, Louisville. Louisville, Chicago, Buffalo, Boston, Columbus, Louisville. None of the above

## At an average cost of 25 cents per mile, the cheapest possible trip that starts at Louisville and passes through each of the other cities exactly once would cost

 \$578.25. \$606.50. \$541.75. \$551.00. None of the above

Questions 10 to 12 refers to the following situation: A hypothetical management science problem requires us to find the cheapest "supercircuit" in a graph. Three algorithms are available: Algorithm 1; Algorithm 2; and Algorithm 3.

Algorithm 1 always produces the cheapest supercircuit. The amount of time it takes to carry out Algorithm 1 doubles every time we increase the number of vertices by one. Algorithm 1 is

 an optimal and efficient algorithm. an approximate and inefficient algorithm. an optimal and inefficient algorithm. an approximate and efficient algorithm None of the above

Algorithm 2 sometimes produces the cheapest supercircuit but most of the time it produces a supercircuit that is only close to being the cheapest. The amount of time it takes to carry out Algorithm 2 is: 1 second for a graph with 1 vertex, 2 seconds for a graph with 2 vertices, ... 5 seconds for a graph with 5 vertices, etc. Algorithm 2 is

 an approximate and inefficient algorithm. an optimal and efficient algorithm. an approximate and efficient algorithm. an optimal and inefficient algorithm. None of the above

Algorithm 3 never produces a supercircuit that is off by more than 10% from the cheapest supercircuit. The amount of time that it takes to carry out Algorithm 3 is: 1 second for a graph with 5 or less vertices; 30 seconds for a graph with 6 vertices; 40 seconds for a graph with 7 vertices, and so on, increasing by 10 seconds every time we add a vertex (from 7 vertices on). Algorithm 3 is

 an approximate and inefficient algorithm. an approximate and efficient algorithm. an optimal and inefficient algorithm. an optimal and efficient algorithm. None of the above

## The repetitive nearest neighbor algorithm for solving the Traveling Salesman Problem is

 an approximate and inefficient algorithm. an approximate and efficient algorithm. an optimal and efficient algorithm. an optimal and inefficient algorithm. None of the above

## n! =

 None of the above

## In trying to solve a certain traveling salesman problem you find a solution with a total length of X miles. If the length of the optimal solution is L miles, then the relative error of your solution is

 None of the above