Problem Set #3

CS 155 -- due November 1, 1999

  1. Apply Dijkstra's algorithm to the single source shortest paths instance whose cost matrix is given below. Express your answer as a sequence of edges in the order in which the algorithm includes them. Assume that vertex 1 is the source vertex. 
               1   2   3   4   5   6   7   8
           0   8   7   3  10  20   1  99
          15   0   6   1   2  99  17  11
           7  10   0  99  21  10   7   9
           8   5   3   0   6  13   9  99 
           3  99  11  12   0   4  22  12
           4   1   9  99  26   0  99   8  
           2   4  99   5  18  99   0  25      
          99  25   2   3   9   7  99   0

  2. Apply the Huffmann algorithm to the sequence of length 12 consisting of the first 12 letters of your name. If your name does not have 12 letters, continue with the letters of the string FROWZYTHINGSPLUMBVEXDJACKQ. In case of duplicate letters, subscript them so that they are different. Let the weight of each letter be given by its position in the English alphabet, so that F has weight 6, R has weight 18, etc.

  3. Recall that in the integer knapsack problem, any item may be included in a solution any integer number of times. Construct an instance of the integer knapsack problem with capacity 20 such that the greedy algorithm that considers items in nonincreasing order of profit density does not find an optimal solution.