ALL types of variables are INTEGERS. Assume any array is of length N
int Gravity[N]
int AdjMat[N][N]
int PathLengths[N][N]
int CurGravityPath[N];

Exhaustive() is called without any arguments
Permute(N)  is called with N

int CheckGravity() does not have any arguments, returns an integer 
int nextAdj(int from, int last) has two integer arguments, returns an integer 



Compute both the average and worst case of 
1. Exhaustive, 
2. Permute, 
3. CheckGravity, and 
4. nextAdj 
Give me the detailed running time that includes all multipliers and the
actual constant. To compute constants, ONLY count assignment statements (do not
try to evaluate the running time of a for loop header).
E.g.;
for( i=0; i<N; i++)
   j=j+1
   k= k+1
has a runing time of 2N. The loop has two statements, each of which
are run N times.
----------------------------------------------------------------
int CheckGravity()
{
   // nextVertex, V, min, hold are all integers 

   for (src=0; src <N; src++) {
      for(dest=0; dest<N; dest++) {
	for (i=0; i<N; i++)
	   CurGravityPath[i]=-1;
	if (src!==dest) {
 	  count=0;
	  CurGravityPath[i]=src;

    	  nextVertex = src;
    	  //This loop processes a portion of the array 
    	  while (nextVertex != dest) {
	   V = nextAdj(nextVertex, -1);
       	   min= abs(Gravity[V]-Gravity[dest]);
	   hold=V;
	   V = nextAdj(nextVertex, V);

	   // -1 marks end of list. Find the end of the list
	   while (V != -1) {
	    if ( abs(Gravity[V ]-Gravity[dest]) < min) {
		min=abs(Gravity[V]-Gravity[dest]);
		hold=V;
	    }
	   	V = nextAdj(nextVertex, V);
	   }
	   nextVertex = hold;
	   count++;
	   CurGravityPath[i]=hold;
	  }
	  if(PathLengths[src][dest] ! = count) {
	    return 0;
	  }
      } // end if
     } // end dest loop
  } // end src loop
  return 1;
}

int nextAdj(int from, int last)
{
   i=last+1;
   index=0, found=0;

   while (i < N) {
	if (AdjMat[from][i] == 1) {
		index=0;
		found=0;
		while(CurGravityPath[index] != -1 && !found){
		   if(CurGravityPath[index] == i)
			found=1;
		   else
		        index++;
		}
		if (!found) 
			return i;	
	}
	i++;
   }
   return -1;
}
------------------------------------------------------------------

void Exhaustive()
{
   for (i=0; i < N; i++) {
      for (j=0; j < N; j++) {
	if (AdjMat[i][j] == 0)
		PathLengths[i][j]=999999999;
 	else {
		PathLengths[i][j]=1;
	}
      } 
      PathLengths[i][i]=0;
   } 

   for (k=0; k<N; k++) {
    for (i=0; i<N; i++) {
      for (j=0; j<N; j++) {
        if ( PathLengths[i][k] + PathLengths[k][j] < PathLengths[i][j])
        {
           PathLengths[i][j] = PathLengths[i][k] + PathLengths[k][j];
        }
      }
    }
  }

} 
---------------------------------------------------------------------
void Permute(int n){
  if (n == 1)
  {
    return;
  }
  else {
    for (i=0; i < n; i++) {
      Permute(n-1);
      tmp=Gravity[n-1];
      if (n % 2 == 1) //n is even
      {
	Gravity[n-1]= Gravity[0];
	Gravity[0]=tmp;
      }
      else            // if n is even
      {
	Gravity[n-1]= Gravity[i];
	Gravity[i]=tmp;
      }
    }
  }
}