Analysis of Algorithms, part 1, CS 288,
May 8, 2006

 

  1. Trace the behavior of Dijkstra's algorithm on the single-source spanning problem for the weighted graph with vertex set {0,1,2,3,4,5} and adjacency matrix below. Use vertex 0 as the source vertex. You needn't show any of the details of the EXTRACT-MIN step. However you should show the contents of the distance array d and the predecessor array π at the begining of each iteration, and finally. You should also show the shortest path computed by the algorithm from the source vertex to each of the other vertices.
         0  2  9  3  7  9
     2  0  6  7  4  6
     9  6  0  8  3  5
     3  7  8  0  5  4
     7  4  3  5  0  3
     9  6  5  4  3  0

     

  2. The following is an outline of a proof by contradiction of the correctness of Kruskal's algorithm. Complete the proof by justifying each step in the outline. The outline assumes that K is the spanning tree found by Kruskal's algorithm, that K is not optimal, and that O is the optimal spanning tree with the latest first difference from K -- that is, if e is the cheapest edge in K that is not in O, then for every other optimal spanning tree O', there is an edge that is at least as cheap, and is in K but not in O'. Note that if K isn't optimal, there must be such an O.
    1. If e is added to O to get a graph G, a cycle will be created.
    2. This cycle contains an edge f that's not in K.
    3. When f is removed from G, the result is a spanning tree
    4. This resulting spanning tree O" is optimal
    5. O" has a later first difference from K than O does, contradicting the choice of O. So K is optimal.

     

  3. Trace the behavior of the simplex algorithm on the linear programming problem that asks for the maximum value of x1 + x2 + x3 subject to x1 + x2 = x3 and x2 + x3 <= 4. Note that the first constraint is an equality constraint rather than an inequality constraint.

    Feel free to use your intuition and other approaches to the problem to check your computation, but except for a maximum of 6 points of partial credit, you will be graded on your use of the simplex algorithm.