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.
(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.
(a) n + n2
(b) 2n + n2 + 2n + 2/n
(c) (n+1)/(n-1)
(d) 2n + 3n + 4n + 5n
(e) n2 + 100n + 10000
Answer:
(a) O(n2)
(b) O(2n)
(c) O(1)
(d) O(5n)
(e) O(n2)