ICS 1F, Homework 6 Solutions

1. Suppose you have offices in five cities, Anchorage, Portland, Seattle, San Francisco, and Los Angeles, that you wish to connect up by a communications network. The costs to connect each pair of cities are

 Anchorage - Los Angeles \$1400 Anchorage - Portland \$1200 Anchorage - San Francisco \$1300 Anchorage - Seattle \$1500 Los Angeles - Portland \$900 Los Angeles - San Francisco \$1000 Los Angeles - Seattle \$700 Portland - San Francisco \$600 Portland - Seattle \$300 San Francisco - Seattle \$500

(a) What is the minimum cost of a communications network connecting all your offices? (I.e., what is the minimum spanning tree.) Draw this network.

Answer: the minimum-cost network uses links connecting Portland-Seattle, SF-Seattle, LA-Seattle, and Anchorage-Portland. Its cost is \$300 + \$500 + \$700 + \$1200 = \$2700.

(b) Some types of network require the offices to be connected into a single loop (so the cheapest network is the same as the solution to the traveling salesman problem). Does there exist an algorithm for solving this problem? Draw the best such network you can find.

Answer: yes, there exists an algorithm, for instance brute force search (trying all possible loops), but it is not efficient. In this case there are 24 different loops (the general formula is that n cities would have (n-1)! loops).

I believe the shortest loop is Anchorage - Los Angeles - Seattle - Portland - San Francisco - Anchorage, with total cost \$4300.

One way to see that this is best involves splitting the loop into the part going into and out of Anchorage, and the remaining four-city path. Los Angeles - Seattle - Portland - San Francisco is the shortest four-city path not involving Anchorage, so any better loop would have to improve on the part of the tour going into and out of Anchorage. But there are only two combinations of cities (San Francisco and Portland, or Los Angeles and Portland) for which the cost into and out of Anchorage is better, and neither combination gives a better overall loop.

2. For each of the following functions, state whether or not a program having the function as its running time would be a polynomial-time program.

(a) time(n) = 4n3 + 3n + 3
(b) time(n) = 2n log n + 30n
(c) time(n) = n1.5
(d) time(n) = 2n log n

Answer: Yes for a, b, and c; no for d.

3. For each of the following functions of a single parameter n, simplify it as much as possible using O-notation. For instance, if the function is 4n3 + 3n + 3, you should simplify it to O(n3).

(a) n + n2
(b) 2n + n2 + 2n + 2/n
(c) (n+1)/(n-1)
(d) 2n + 3n + 4n + 5n
(e) n2 + 100n + 10000