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

 

  1. Adjacency lists are most efficient in every case except for the Floyd-Warshall algorithm. The other algorithms would have Ω(n2) time complexity if adjacency matrices were used, and all have strictly better time complexity using adjacency lists. In each of these algorithms, the only time we look at the graph is to find the set of vertices adjancent to a given vertex. By contrast, in the Floyd-Warshall algorithm we need to check each pair (i,j) of vertices to find the weight of the edge between vertex i and vertex j, even if there's no such edge in the graph.

     

    1. The binomial heap resulting from the algorithm would be
         22----------------------6
    |                      |                       
   23          7----29-10-44                      
               |     |  |          
        15-18-25 48-31 17     
         |  |     |           
     28-33 37    56                     
      |
     41
      Other correct representations of the merged heap are obtainable if slight variations on the algorithm are used.
    2. The result of insertion would be the resulting of applying the algorithm to the original binomial heap and the binomial heap whose only element is the element to be inserted.
    3. The minimum element M may be found by a (short) sequential search through the roots of the binomial trees that make up the binomial heap. The resulting binomial heap may be found by merging the binomial heaps whose trees are
      • the trees rooted at the children of M, and
      • the trees of the original binomial heap, excluding the tree rooted at M
      Note that in the representation of Cormen et al the second of these sequences would have to be reversed to obtain a legal representation of a binomial heap.
     

    1. For dense graphs, the time complexity of Prim's algorithm is asymptotically superior to that of Kruskal.
    2. If there are edges with negative weights
    3. For sparse graphs
    4. If merging of heaps is a common operation
    5. In most cases, the simplex algorithm, although not a polynomial-time algorithm, works faster in practice than the ellipsoid algorithm.