Quiz 6: October 29, 2004

1. Write a method called maximumDegree of the MyMatrixGraph class that returns the maximum degree of any vertex in the graph. Here is part of the function; you'll have to complete it.
   (Hint: This function runs in O(n^2) time.)

   		int maximumDegree()
   		{
   			int maxDeg = 0;
   			for(int i = 0; i < numVertices; i++)
   			{
   
   				Vector nbrs = getNeighbors(map[i]);	
   				if(nbrs.size() > maxDeg)
   					maxDeg = nbrs.size();
   			}
   
   			return maxDeg;
   		}
   

2. Write a method called maximumDegree of the MyListGraph class that returns the maximum degree of any vertex in the graph. Here is part of the function; you'll have to complete it. It is required that this function run in O(n) time.

                   int maximumDegree()
                   {
                           int maxDeg = 0;
                           for(int i = 0; i < numVertices; i++)
                           {
   				int temp = ((DoublyLinkedList)adjList[i]).size();
                                   if(temp > maxDeg)
                                           maxDeg = temp;
                           }
   			return maxDeg;
                   }
   

   Notes:
   The first function runs in O(n^2) time because the for-loop has n iterations and in each iteration, the function getNeighbors() is called and this takes O(n) time to execute. It is possible to implement this function without calling getNeighbors() and just scanning row i of the adjacency matrix and count the number of 1's (or true's). The running time of this alternate implementation would be the same. The second function takes O(n) time because getting the size of the doubly linked list that contains the neighbors of the vertex i, takes O(1) time, for each i. Since the for-loop executes n times, the total running time is O(n).

   ---