CSC212 Lab 9 Solutions 2014

--D. Thiebaut (talk) 15:46, 23 October 2014 (EDT)

---

Problem #1

public class Lab9 {

        private static int[] initSortedArray( int N ) {
                int[] array = new int[N];
                array[0] = 3;
                for ( int i=1; i<N; i++ ) 
                        array[ i ] = array[i-1] + (i*11)%7;
                
                return array;
        }
        
        private static int[] initArray( int N ) {
                int[] array = new int[N];
                array[0] = 3;
                for ( int i=1; i<N; i++ ) 
                        array[ i ] = (i+1) * 101 % 23;
                
                return array;
        }
        
        private static int fact( int n ) {
                // stopping condition
                if ( n==1 ) 
                        return 1;
                
                // recursive step
                return n * fact( n-1 );
        }
        
        private static int sum1( int[] A, int low, int high ) {
        	if ( low > high ) return 0;
        	if ( low == high ) return A[low];
        	int keep = A[low];
        	return keep + sum1( A, low+1, high );
        }

        private static int sum2( int[] A, int low, int high ) {
        	if ( low > high ) return 0;
        	if ( low == high ) return A[low];
        	int keep = A[high];
        	return keep + sum2( A, low, high-1 );
        }

        private static int sum3( int[] A, int low, int high ) {
        	if ( low > high ) return 0;
        	if ( low == high ) return A[low];
        	int mid = (low+high)/2;
 
        	return sum3( A, low, mid-1 ) + A[mid]+ sum3( A, mid+1, high );
        }

        private static int max( int[] A, int low, int high) {
        	if ( low==high ) return A[low ];
        	int keep = A[low];
        	int otherMax = max( A, low+1, high );
        	if ( keep > otherMax ) return keep;
        	return otherMax;
        }
        
        static int counter = 0;
        private static int binSearch(int key, int[] A, int low, int high ) {
        	if ( low > high ) return -1;
        	
        	int mid = ( low+high )/2;
        	counter++;
        	if ( key == A[mid] )
        		return mid;
        	
        	counter++;
        	if ( key < A[mid] )
        		return binSearch( key, A, low, mid-1 );
        	return binSearch( key, A, mid+1, high );
        }
        
        private static void displayArray( int[] A ) {
        	for ( int i=0; i<A.length; i++ )
        		System.out.print( A[i] + " " );
        	System.out.println();
        	
        }
        public static void main(String[] args) {
        	int N = 20; 
        	int A[] = initArray( N );
        	
        	displayArray( A );
        	
        	System.out.println( "Sum1 = " + sum1( A, 0, A.length-1) );
        	System.out.println( "Sum2 = " + sum2( A, 0, A.length-1) );
        	System.out.println( "Sum3 = " + sum3( A, 0, A.length-1) );
        	System.out.println( "max = " + max( A, 0, A.length-1) );
        	
        	A = initSortedArray( N );
        	int keys[] = new int[] { 3, 34, 63, 0, 100 };
    		displayArray( A );
        	for ( int i=0; i<keys.length; i++ ) {
        		System.out.println( "binSearch(" + keys[i] + " ) = " 
        				+ binSearch( keys[i], A, 0, A.length-1 ) );
        	}
        	
        	N=100000000;
        	System.out.println( "N = " + N );
        	A = initSortedArray( N );
        	for ( int i=0; i<keys.length; i++ ) {
        		counter = 0;
        		System.out.println( "binSearch(" + keys[i] + " ) = " 
        				+ binSearch( keys[i], A, 0, A.length-1 )
        				+ " " + counter + " probes");
        	}
        	
        }
}

Maze Problem

Playing With Directions

There are several ways to do this. One is to change the for loop:

         // original
         for ( int dir = 0; dir < 4; dir++ ) 
               switch ( dir ) {
                                case 0: newi = i-1; newj=j;   break;
                                case 1: newi = i;   newj=j+1; break; 
                                case 2: newi = i+1; newj=j;   break;
                                case 3: newi = i;   newj=j-1; break;
                             }

or

         // reverse the loop
         for ( int dir = 3; dir >=0; dir-- )  
              switch ( dir ) {
                                case 0: newi = i-1; newj=j;   break;
                                case 1: newi = i;   newj=j+1; break; 
                                case 2: newi = i+1; newj=j;   break;
                                case 3: newi = i;   newj=j-1; break;
                             }

or, create an array with preset directions: in this case, we want to go up first, down next, right, then left.

         // create an new array of directions:
         int[] dirs = new int[] { 0, 2, 1, 3 };
         for ( int k = 0; k <4; k++ )  {
               dir = dirs[ k ];
               switch ( dir ) {
                                case 0: newi = i-1; newj=j;   break;
                                case 1: newi = i;   newj=j+1; break; 
                                case 2: newi = i+1; newj=j;   break;
                                case 3: newi = i;   newj=j-1; break;
                             }

Cleaning Up The Maze at the End

       /**
         * clears the maze of 'b' (back-tracks) or '.'
         * and marks the path to the exit with '.'
         */
        private static void clearMaze() {
                for ( int i=0; i< maze.length; i++ ) 
                        for ( int j=0; j < maze[i].length; j++ )
                                if ( maze[i][j] == '.' || maze[i][j] == 'b' )   
                                        maze[i][j] = ' ';
                                else if ( maze[i][j] == '*' )
                                        maze[i][j] = '.';
        }

N-Queens

• To count the number of probes, all I did was to add a static member variable called counter to the class. This member variable is available in every method, so I don't need to pass it as a parameter to any of the already written methods. See the code here, and just search for "counter" to see where I put the counter++ statements. I didn't add them to the display functions, because these are just for debugging or visual information, but are not needed to find the solution.

You can quickly test your program by running a shell loop form the command line.

In the tcsh shell (the default on beowulf2), just go to the directory where your NQueens.class file is located, and type:

foreach N ( `seq 5 25` )
java NQueensCountProbes $N
end

Dim= 5x5 # of probes = 42 
Dim= 6x6 # of probes = 563 
Dim= 7x7 # of probes = 126 
Dim= 8x8 # of probes = 2703 
Dim= 9x9 # of probes = 1055 
Dim= 10x10 # of probes = 3001 
Dim= 11x11 # of probes = 1655 
Dim= 12x12 # of probes = 9240 
Dim= 13x13 # of probes = 4213 
Dim= 14x14 # of probes = 77545 
Dim= 15x15 # of probes = 60014 
Dim= 16x16 # of probes = 461338 
Dim= 17x17 # of probes = 268325 
Dim= 18x18 # of probes = 2102315 
Dim= 19x19 # of probes = 140870 
Dim= 20x20 # of probes = 11151705 
Dim= 21x21 # of probes = 513048 
Dim= 22x22 # of probes = 104166319 
Dim= 23x23 # of probes = 1636724 
Dim= 24x24 # of probes = 26959471 
Dim= 25x25 # of probes = 3435825 

The first observation is that the number of probes, which is indicative of the amount of time taken, is not necessarily directly proportional to the size of the chessboard. For example it take less time to find the first solution for a 19x19 board than an 18x18 board.

Actually the time complexity of N-Queens as we have implemented it is O( 2^N ) (see this site for reference), or exponential. It will grow very quickly in number of steps as we increase the board size, making it very time consuming to find solutions as N increases.