csc148, Spring 1998

Revision to Assignment 4

Do not hand in Part A. And for Part E, solve the problem below rather than what appears on the original handout.

Part E -- Big-oh (part deux)

In Assignment 2, you implemented an algorithm that two-colours a graph. In this part, you will analyze the complexity of that algorithm.

Assume that all operations in Graph and SetOfInts are O(1). (Examples are removing an integer from a SetOfInts, and adding an edge to a Graph.) Also, assume that there are n vertices in the Graph.

Answer the following questions:

1. Describe briefly what kind of nodes are in each of the following sets at any one time: in set S; in set C; in both set S and set C; in neither set S nor set C.
2. In terms of which edges are present in a graph, what is the worst (most time-consuming) situation for the algorithm? Explain.
3. In this worst case, how often is the outermost loop executed?
4. How many times can a particular vertex be removed from S, and why?
5. How many times can a particular vertex be inserted into C, and why?
6. Based on these answers and the assumptions made above, analyze the worst-case running time of algorithm 2-colour. Use big-oh notation, and explain all of your steps.
7. If removing a vertex from a SetOfInts is O(n), rather than O(1) as we assumed earlier, how is the worst-case running time of 2-colour affected?

For your convenience, here is the algorithm. Analyze this, not your own Java code!

 
// Colours are 0,1 
// Precondition: every vertex v has been initialized 
//   so that v.colour == -1.
Algorithm 2-colour(Graph <V,E>)
    S = V ;
    while (S not empty) {
        Pick one vertex v in S and remove it from S ;
        v.colour = 1 ;
        C = {v} ;
        while ( C not empty ) {
            Pick one vertex u in C and remove it from C ;
            for ( each vertex w adjacent to u ) {
                if ( w.colour == -1 ) {
                     Remove w from S ;
                     w.colour = 1 - u.colour ;
                     C = C union {w} ;
                else if ( w.colour == u.colour ) {
                     return false ;
                }
            }
        }
    }
    return true ;
end 2-colour