Quiz #1

[Skip Breadcrumb Navigation]

Home

Chapter6:

Quiz #1

This activity contains 15 questions.

The number of Hamilton circuits in is

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:

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 algorithmNone 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

The Submit Answers for Grading feature requires scripting to function. Your browser either does not support scripting or you have turned scripting off.

So, the Submit Answers for Grading button below will not work.

The following Submit Answers for Grading button is provided in its place and will clear your answers:
The Clear Answers and Start Over feature requires scripting to function. Your browser either does not support scripting or you have turned scripting off.

So, the Clear Answers and Start Over button below will not work.

The following Clear Answers button is provided in its place and will clear your answers:

Your browser either does not support scripting or you have turned scripting off. Because of this, the answer choices will NOT appear in a different order each time the page is loaded, though that is mentioned below. Note that you do not need this feature to use this site.

Answer choices in this exercise appear in a different order each time the page is loaded.