CSC212 Lab 9 Solutions 2014
--D. Thiebaut (talk) 15:46, 23 October 2014 (EDT)
Contents
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.
