CS410, Summer 1998
Quiz #14
August 5

Consult no sources.				Name:

1. What are the strongly-connected components of a dag?

2. What is a minimum spanning tree?

3. What is a cut and what is a light edge of a cut?

4. What is the running time of Kruskal's algorithm?  What is the slowest
   part of the algorithm?


ANSWERS
=======

1. The vertices.							2.5
   -1   for "no SCC"
   -1.5 for giving the only the algorithm for finding SCC's

2. A set of edges such that:
   The graph using only those edges is connected.			1.5
   The sum of the weights of the edges is less than or equal to the
     sum of the weights of any other such subset of edges.		1

3. A cut is a partition of the vertices into two			1
	disjoint sets (S, V-S)						0.5
   A light edge is the that crosses the cut	 			0.5
	 with the lowest weight						0.5


4. O(mlogm)								1
   m is the number of edges						0.5
   Sorting the edges by weight is the slowest part 			1