Assignment 9 due by the end of class Wednesday March 28 2001.

Recall that in class we covered the following algorithms last week:

  1. Recall that unweighted single source shortest paths can be computed in linear time. Briefly describe an algorithm to compute unweighted shortest paths between all vertex pairs, and give its complexity (with justification).
  2. Recall that transitivity of a relation R means a R b & b R c implies a R c. Also recall that to compute the transitive closure of a graph means to compute all transitive edges and to add them to the graph. By modifying Floyd's algorithm, give an efficient algorithm to compute the transitive closure of a graph. Also, give your algorithm's complexity (justify briefly).
  3. How many topological sorts exist for (a) a total order on 7 vertices, and (b) this partial order? Hint: trace the algorithm from class.
     1   2
      \ / \
       3   4
        \ /
         5
    
  4. Show or give a counter-example:
    (a) Dijktra's algorithm works with negative weighted edges.
    (b) Floyd's algorithm works with negative weighted edges.
  5. Describe briefly how you would solve the following problem: given a maze constructed from a square grid (empty locations are represented by spaces, walls by X's, movement from a location is by one of the four horizontal/vertical directions), a starting location S, and a destination D, describe a shortest sequence of moves which gets from the start to the finish.
    An example is shown below.
    XXXXXXXXXXXXXXXXXXXX
    X       D          X
    XXXXXXXXXX  X  X  XX
    X  X XX  X  XXXX  XX
    X  X  X  X  X  X  XX
    X  XX X  X  X  XXXXX
    X  X SX  X  X  X  XX
    X  X  X  X  X  X  XX
    X                  X
    X XX XXX   XX X XXXX 
    X                  X
    XXXXXXXXXXXXXXXXXXXX
    
    Bonus: how would you solve the problem if the sequence must encounter *several* destinaion locations (in any order), and again be a shortest sequence?