Answers to Problem Set #3

CS 155 -- due November 1, 1999

  1. The successive values of the cost vector are shown below. The cost of the shortest path to an edge in the set S of vertices whose optimal path cost has already been found are not shown -- the cost is that of the final entry in the given column. The cheapest paths therefore have respective costs 0, 5, 6, 3, 7, 11, 1, and 15; the paths are those of the spanning tree whose edges are (in order of generation) (1,7), (1,4), (7,2), (4,3), (2,5), (5,6), and (3,8). 
      1   2   3   4   5   6   7   8      
  0   8   7   3  10  20   1  99       include the edge (1,7)
      5   7   3  10  20      26       include the edge (1,4)
      5   6       9  16      26       include the edge (7,2)
          6       7  16      16       include the edge (4,3)
                  7  16      15       include the edge (2,5)           
                     11      15       include the edge (5,6)
                             15       include the edge (3,8)
  2. Using for example the first 12 characters of the string
    FROWZYTHINGSPLUMBVEXDJACKQ
    we get (after sorting by weight) the 12 character/weight pairs
    F/6, G/7, H/8, I/9, N/14, R/18, O/15, S/19, T/20, W/23, Y/25, Z/26
    The resulting tree is 
                                190 
                       /          \ 
                  80                  110 
                /    \             /      \ 
             37        43        51        59 
            / \       / \       / \       /  \ 
           R   S     T   W     Y   Z    27     32 
                                       / \     / \ 
                                      13  N   O  17 
                                     / \         / \ 
                                     F  G       H   I
  3. One solution: Let n=2, let the weights be 8 and 5, and the profits (or values) be 16 and 9. The greedy solution would include only 2 copies of the first item, for a profit of 32, while the optimal solution uses 4 units of the second item for a profit of 36.