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.
(a) time(n) = 4n3 + 3n + 3
(b) time(n) = 2n log n + 30n
(c) time(n) = n1.5
(d) time(n) = 2n log n
(a) n + n2
(b) 2n + n2 + 2n + 2/n
(c) (n+1)/(n-1)
(d) 2n + 3n + 4n + 5n
(e) n2 + 100n + 10000