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