- will go over old quiz on monday
- pass out course evaluations (FCEs) today
- dynamic programming for shortest paths (Floyd)
- transative closure on graphs

Floyd's Algorithm:

  Uses adj matrix representation of a graph. (Use same example as
  11/12 section)

		       2
                a ---------- b
		|            |
	        |            |5
	       1|            |
		|            |   2
		d -----------c-------e
		      1

Here we put in a[i][j] the distance between i & j, where 
	a[i][i] = 0
	a[i][j] = INF, if there is no edge between i and j

for the above matrix we have:

	    a	b   c	d   e
	 +--------------------	
	a|  0   2   I   1   I		(I == infinity)
	b|  2   0   5   I   I
	c|  I   5   0   1   2
	d|  1   I   1   0   I
	e|  I   I   2   I   0


  Goal is to create a matrix B such that B[i][j] = min length from i to j
  in the graph specified by adjacency matrix A.

  Here's the code:

findmin(A) {
  /* make a copy of the adjacency matrix */

  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      B[i][j] = A[i][j];

  /* after each iteration of the outside loop, B[i][j] = len of i->j 
     path through vertices in the set 0..k  <- example of DP */

  for (k = 0; k < N; k++)
    for (i = 0; i < N; i++)
      for (j = 0; j < N; j++)
        B[i][j] = min( B[i][j], (B[i][k] + B[k][j]);
}
        
  Draw a picture to show where we get the following line of code:

        B[i][j] = min( B[i][j], (B[i][k] + B[k][j]);

  How much time does this algorithm take?  O(N^3) time.

Lets run algorithm (Try and remember previous squaring algorithm)

when k = 'a': fill in b,d = 3
when k= 'b':  fill in a,c = 7 (not shortest, just shortest through set {a,b}
when k = 'c': fill in a,e = 9; b,e = 7; d,e = 3
when k = 'd': fill in a,c = 2; a,e = 4; b,c = 4, b,e = 6

  Point out the differences between this algorithm and the repeated
  squaring algorithm described 2 section ago.

  a) this algorithm is faster (N^3 vs. N^3 log N)
  b) by the time we complete the k'th iteration of this algorithm,
     we have found all paths that using only vertices from the set
     0..k as intermediate vertices

     in the other algorithm, computing the matrix A^k will find all
     paths of length k or less

2) Warshell's Algorithm for transative closure is same as Floyd's
   except: min is replaced with the || operator, and + is replaced with &&

	explain what transative closure is.

  Draw a picture to show where the following line of code comes from:

        B[i][j] = B[i][j] || (B[i][k] && B[k][j]);

----------------------------------------------------------------
If time and inclination show how the proof of prim's algorithm fails
if the edges are directed (don't necc get the cycle).

	Note: the Dijkstra algrorithm for shortest paths works even if
	you have directed edges (but all lengths are positive).  However, the
	spanning tree algorithm DOESN'T work.  If you want, you can
	try to figure out where the proof breaks down.

	Here's an example (A is the start)
              3
           A---->B
           |     |
	  4|     |3
           v     v
           C---->D
              1