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 30` )
java NQueensCountProbes $N
end

5x5 board: 42 probes. real time = 0 ms.
6x6 board: 563 probes. real time = 0 ms.
7x7 board: 126 probes. real time = 0 ms.
8x8 board: 2703 probes. real time = 0 ms.
9x9 board: 1055 probes. real time = 0 ms.
10x10 board: 3001 probes. real time = 0 ms.
11x11 board: 1655 probes. real time = 0 ms.
12x12 board: 9240 probes. real time = 0 ms.
13x13 board: 4213 probes. real time = 0 ms.
14x14 board: 77545 probes. real time = 15 ms.
15x15 board: 60014 probes. real time = 15 ms.
16x16 board: 461338 probes. real time = 46 ms.
17x17 board: 268325 probes. real time = 34 ms.
18x18 board: 2102315 probes. real time = 106 ms.
19x19 board: 140870 probes. real time = 28 ms.
20x20 board: 11151705 probes. real time = 149 ms.
21x21 board: 513048 probes. real time = 45 ms.
22x22 board: 104166319 probes. real time = 614 ms.
23x23 board: 1636724 probes. real time = 108 ms.
24x24 board: 26959471 probes. real time = 228 ms.
25x25 board: 3435825 probes. real time = 110 ms.
26x26 board: 28162714 probes. real time = 250 ms.
27x27 board: 34276317 probes. real time = 256 ms.
28x28 board: 230008614 probes. real time = 1210 ms.
29x29 board: 122909720 probes. real time = 685 ms.
30x30 board: 225714358 probes. real time = 22846 ms.

If you prefer to use the bash shell, you can write your loop as follows:

 for N in `seq 8 25`; do
     java NQueensCountProbes $N
 done

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.

Note

You will find that the number of probes grows so fast, that it actually overflows the int type for counter. A long will quickly be necessary, but soon enough, we may want to move on to the BigInteger type.