Analysis of Algorithms, part 2, CS 288, May 9, 2007

Analysis of Algorithms, part 2, CS 288,
May 9, 2007

For each of the graph algorithms below, state whether an adjancency matrix representation or an adjacency list representation for graphs gives the most efficient version of the algorithm. Justify your answer in each case.
1. Prim's algorithm
2. Kruskal's algorithm
3. Dykstra's algorithm
4. the Floyd-Warshall algorithm
5. the topological sort algorithm of the main text of Cormen et al
1. (12 points) Show how the BINOMIAL-HEAP-UNION algorithm would merge the two binomial heaps
```
 
                      6-----23----18
                      |            |
               29-10-44           37 
                |  |
            48-31 17
             |
            56
```
  and
```
 
            15-- 7----22
             |   |
         28-33  25
          | 
         41
```
  In the diagrams for these binomial heaps the children of the same parent are linked together, so that the binomial heap often represented as
```
       3----1----2
      /|    |
     4 6    5
     |
     7
```
  is instead represented as
```
         3----1----2
         |    |
     4---6    5
     |
     7
```
  Don't forget to show the resulting binomial heap (you may use either sort of diagram).
2. (4 points) Describe briefly how the BINOMIAL-HEAP-UNION algorithm can be used to insert elements into a binomial heap.
3. (4 points) Describe briefly how the BINOMIAL-HEAP-UNION algorithm can be used to find and extract the minimum elements of a binomial heap.
Under what circumstances might someone prefer to use
1. Prim's algorithm instead of Kruskal's algorithm for the minimum spanning tree problem?
2. The Bellman-Ford algorithm instead of Dijkstra's algorithm for the single-source shortest paths problem?
3. Johnson's algorithm instead of the Floyd-Warshall algorithm for the all-pairs shortest paths problem?
4. binomial heaps instead of ordinary binary heaps?
5. the simplex algorithm instead of the ellipsoid algorithm (the first polynomial-time algorithm discovered for the linear programming problem)?