Question 1
The brute-force algorithm for solving the Traveling Salesman Problem is
◦ an approximate and inefficient algorithm.
◦ an optimal and inefficient algorithm.
◦ an approximate and efficient algorithm.
◦ an optimal and efficient algorithm.
◦ none of these
Question 2
In applying the brute-force algorithm to solve a traveling salesman problem on a graph with 20 vertices, you use a supercomputer that computes 1 billion (that's 10
9) circuits per second. There are 31,536,000 seconds in a year. Roughly how long would it take for the supercomputer to solve this problem?
◦ approximately 1.5 years
◦ approximately 4 years
◦ approximately 31 years
◦ approximately 15 years
◦ approximately 77 years