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

    Answer:
    (a) O(n2)
    (b) O(2n)
    (c) O(1)
    (d) O(5n)
    (e) O(n2)