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");
        	}
        	
        }
}