# ICS 1F, Homework 6

Due Friday, March 13

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.

(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.

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

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