CSC212 Lab 9 2014

--D. Thiebaut (talk) 15:00, 22 October 2014 (EDT)

---

...

Recursion

• Use the skeleton program below to write different recursive functions.

public class RecurseSkeleton {

	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 );
	}
	
	public static void main(String[] args) {
		int N = 20; 
		int A[] = initArray( N );

		int x, y;
		x = 5;
		
		System.out.println( "fact( " + x + " ) = " + fact( x ) );
	}
}

Problem 1

Sum

• Write a recursive function that will compute the sum of all the elements of an array.
• Think of what we did in class: imagine your being given a chuck of an array, delimited by a beginning and end, take one of the ends to keep, and pass the remaining chuck to somebody else. That person at some point returns the sum of the chuck it got. You take that number, add it to the number you kept, and return the sum to whoever gave you the chunck (your caller).
• Here's an algorithmic version of what we have to do:

1. what we get: a chunk of Array A, delimited by two indexes: low and high.  
2. what we have to do: sum up all the integers between A[low] and A[high] (ends included).
3. we test for the stopping condition: is the chunk that we have received empty, or containing just 1 element?
3.1. if it is empty (low > high), then we return 0.  That's the sum of an empty chunk.
3.2. if it contains only 1 integer (low==high), then we return that element as the sum.
4. Otherwise, the chunk has more than 1 integer in it.
5. we keep one of them.  Say A[low]
6. we pass the remaining chunk, A[low+1 to high] to somebody else (who's running the same algorithm).
7. we get back the sum of that chunk.
8. we add it to what we kept A[low]
9. we return the sum as the sum of the chuck we had received (A[low to high]).

• following this algorithmic definition, implement a recursive function that computes the sum. Here's a skeleton for it:

    static public int sum(  int[] A, int low, int high ) {
          // if chunk empty, return 0

          // if chunk of size 1, return A[low]

          // otherwise...
          //  keep A[low]

          //  compute sum( A, low+1, high ) and save it
          
          //  add what we kept to that sum, and return new sum
          
    }

Keep the high end

• Same exercise, but instead of keeping the low end element, keep the high end element.

Keep the middle element

• Same exercise, but instead of keeping the low or high end element, keep the middle element.
• In this case, you compute mid = (low+high)/2, and keep that. Then you call yourself (recursive call) on a chunk going from low to mid-1, and call yourself again on the chunk going from mid+1 to high. You get 2 sums back, add them to your A[mid] element, and return that.

Max

• Using one of the approaches you investigated with the sum problem above, create a recursive function that computes the max of the array.

Binary Search

Implement Binary Search on a sorted array. The algorithm is simple:

• Main Program:

• Input: A sorted array of size N
• a key, of the same type as the elements of A
• index = binSearch( key, A, 0, N-1 ) // search the key in A, ranging from Index 0 to Index N-1

• binSearch( key, A, low, high )

• if low > high, end of search. Key not found. Return -1
• mid = (high+low) / 2
• if key in A[mid], then key found: return mid as index of key
• if key < A[mid], then key must be in lower part of array, from low to mid-1

index = binSearch( key, A, low, mid-1 )

• otherwise key > A[mid], then key must be in upper part of array, from mid+1 to high

index = binSearch( key, A, mid+1, high )

• return index

• Write the recursive binSearch function. Use the skeleton program introduce earlier, and make sure you initialize the array with sorted ints.
• Make sure it finds keys that are located at the beginning of the array, at the end, in the middle, or recognizes when keys are not in the array.

Counting the Number of Probes

• We refer to the action of looking at an element in an array as a probe.
• Create a static int counter in the class that holds your binary search function, and increment it every time your binSearch function looks at an element in your array. For example:

         counter++;
         if ( array[mid]==key )...

• Make sure you reset the counter to 0 in main(), before you start a search.
• Make your program print the index of where it finds (or not) the key, along with the number of probes required to find it.
• Set N, the dimension of the array, to 20.
• Run a few searches, and get a sense for the number of probes requires.
• Now, set N to 100, and perform a few searches. Look at how the number of probes changes, on the average.
• Set N to 1000. Same exercise.
• Set N to 10,000. Same exercise.
• Set N to 100,000. Same exercise.
• Set N to 1,000,000. Same exercise.
• Set N to 10,000,000. Same exercise.
• Set N to 100,000,000. Same exercise. Isn't it amazing how few probes are needed to search an an array of 100 million ints? That's the power of O( log(n) )!

Recursive RPN Solver

• Below a skeleton for a recursive Reverse-Polish-Notation solver. We assume that the expression it gets to solve are error free.

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class RecursiveRPN {
	
	private static int recurseSolve( ArrayList tokens, Stack<Integer> stack ) {
		// STOPPING CONDITION
                // if the size of the token list is 0, then empty expression: return top of stack
                
                //===> put your code here...

	        // get the next token from the array, the first one, and remove it from the array...	

                //===> put your code here...


 		// DO SOME WORK
                // if the token we got above is a "+", then pop 2 ints from stack, add them up, push sum back in stack.
                // similarly, if token is "-", pop 2, subtract, push difference
                // if token is "*", pop 2, multiply them together, push product
                // if token is "/", pop 2, divide 2 by first, push integer quotient back in stack...

                //===> put your code here...

                // and if token was not a +, -, *, or /, then it must be an int.  push it in the stack...
                // (and be careful, because a token is a string, and the stack holds integers only...)

		
                // RECURSIVE STEP: we've done some work, recurse and pass the remaining tokens and stack
                // to recurseSolve() 

                //===> put your code here...

                // return result...
                //  whatever we get back from recurseSolve, in the recursive step, we pass back...

                //===> put your code here...
	}

	
	static public void main( String[] args ) {
		ArrayList<String> tokens = new ArrayList<String>();
		
		// if user specifies expression on command line, then uses that
		if ( args.length != 0 ) {
			for ( int i=0; i<args.length; i++ )
				tokens.add( args[i].trim() );
		}
		// else use the expression below
		else {
			String expression = "3 5 + 7 3 - *";
			String[] tokenStrings = expression.split( " " );
			for ( int i=0; i<tokenStrings.length; i++ )
				tokens.add( tokenStrings[i] );
		}
		
		// display the tokens, for debugging purposes
		System.out.println( "tokens = " + tokens );
		
		// create a stack
		Stack<Integer> stack = new Stack<Integer>();
		
		// solve expression recursively
		int x = recurseSolve( tokens, stack );
		
		// display result.
		System.out.println( "result = " + x );
	}
}

• Study the comments left in recurseSolve(), and replace the "//===> put your code here" comments by java code implementing all the operations described.

• Verify that your program works and outputs 32.
• Modify the expression in main() and solve something a bit more complicated. Say, "12 34 56 + + 3 - 5 9 + * 10 /", which should evaluate to 138.

Submission To Moodle

• Submit your recursive RPN solver program to Moodle, "Week 8, Lab 9" Section.
• (The submission deadline is Friday night at 11:55 p.m.)

Maze Exploration

• Copy the code from this page.
• Run the code. You may get a better experience running this in a Terminal/Console window than in Eclipse.
• You can adjust the speed of the display by changing the constant in

Thread.sleep(100);

100 means 100ms, or 1/10th of a second between steps of the algorithm. 1000 would be 1 second; very slow. 10 would be 1/10th of a second between refresh operations: very fast.

• Try different mazes by calling createMaze(), or createMaze1(), or createMaze2() at the beginning of main().
• Create your own maze by copying createMaze1() as a new function called createMaze3(), and by editing it to create a different rectangular maze. You can change the number of rows or columns. If you change the number of rows, you should update the variable dim. The program will automatically adapt to the number of columns. You do not have to change any variable anywhere for this.

Changing the Direction of Exploration

• Study the recurseVisit() function, and change the way the visiting is done. In its original version, the visiting always goes top first, then right, then down, then left, in order of priority and possibility.
• Play with different ordering of directions
• Change the ordering of directions so that the visiting of the following maze is much faster than with the original code:

                "###############" 
                "       #      #" 
                "#      #      #"
                "E      #      #"
                "#             #" 
                "#             #" 
                "#             #" 
                "#             #" 
                "#             #" 
                "###############"

Cleaning-Up the Maze

• When a successful visit completes, a lot of characters are left in the maze, including breadcrumbs (.), backtracks (b), and successful steps (*).
• Add a new function called clearMaze() that you will call at the end of the program, and that will leave only the path to the exit. Make the successful path to the exit show up as series of dot characters.
• Test your function on the first maze of the program.
• Verify that the last maze displayed looks like this:

###############
......#   #...#
#####.# ###.#.#
#...#.  # #.#.#
#.#.#.### #.#.#
#.#.#.# # #.#.#
#. ...#...#.#..
#.#####.#.#.# #
#.......#...# #
###############
Success!  Found a path.

N-Queens Problem

• Get the code from this page.
• Play with it. Observe the recursion as the program attempts to put 8 Queens on the 8x8 board.
• Watch how the algorithm finds a solution for N = 7.
• Now, change N to 20. Observe how the recursion works...
• You may want to decrease the sleep time to 0 to see the algorithm going full speed (although the displaying of the maze slows it down tremendously)

Speeding up the Recursion

• Modify the program so that it displays the NxN board only at the end, when it has finished the recursion and found a solution (or not).

Counting the Number of Probes Performed

• Add a global counter to your program, that will count the number of times the program accesses a cell of the board. In other words, increment the counter every time the program uses board[...][...] in an assignment or a test.
• Make your program display the number of probes it has gone through in order to find a solution.
• Run your program for various dimensions, and estimate if the time complexity of the N-Queens program is O(1) (constant), O(N) (linear), O(N^2), or even greater. For this exercise, you can assume that the time taken to execute the program is proportional to the number of probes.

https://sites.google.com/site/nqueensolver/home/algorithm-results

https://sites.google.com/site/nqueensolver/home/algorithms/2backtracking-algorithm