CS125 Fall 2008

Lab # 3

 

In this lab, you will practice writing several recursive methods. Read through this entire lab before starting to write your code.

   

Part 1:  Finding the largest item in an unsorted array:

    

Yesterday in class, we covered several recursive algorithms, one of which found the largest element in an unsorted array. For this part of the lab, you will implement this method both iteratively and recursively. Follow the steps below to get started:

  1. Create a folder called L3 on the desktop.
      
  2. Open DrJava and start a new class called Lab3.java.  There is no need to import or extend any other classes, you will be writing static methods and running them in the DrJava interactions pane.
      
  3. Inside class Lab3, define a public static method called iterativeMaxArray() that returns the maximum valued array item after finding it in the array by scanning through all the array elements in a loop. 
     
    When your program compiles, you can test it in the DrJava interactions pane.  But first, you need to create an array of integers.  The easiest way to create an array of integers in the interactions pane is to use the "declare and initialize" form of an array declaration, as shown below:

        > int[] numArray = {23, 4, 78, 2, 99, 16, 76};

    After creating the array, call method iterativeMaxArray as shown below, passing in  numArray. Running this method with numArray, as given above, as an argument from the interactions pane should look like this:

       > Lab3.iterativeMaxArray(numArray)
        78  
     
  4. Now define a public static method called  recMaxArray() that returns the maximum valued array item. This method should use a "divide and conquer" recursive strategy that repeatedly divides the array in half  until the array contains only one element, in which case the actual value of the element is returned. The italicized phrases in the last sentence emphasize the point that it is more efficient to only conceptually divide the array in half for each recursive call. You can do this by keeping track of continually smaller ranges of indicies in the array. These indicies are passed as parameters (low and high) to each recursive call along with the entire array. 
     
    The figure below illustrates the action of recMaxArray on an array of integers called numArray. The initial call to the recMaxArray method in the interactions pane is
     
      > Lab3.recMaxArray(numArray,0,numArray.length-1)
     
    This figure shows how the midpoint is calculated before each recursive call, what the new values of low and high are for each recursive call, and how the recursion stops and returns when low == high. 

     
    The lower part of the diagram shows the result returned from each recursive call. The value returned is labeled either left or right, depending on which half of the array it is in at the time the recursive call is made.    

    The statement
             
        return (left > right) ? left : right;

    is a short hand way to test each value of left and right returned by the recursive calls, returning the larger value to the next level up in the recursion. We say the recursion "bottoms out" when the numbers 67 and 88 are returned as left = 67 and right = 88. The value 88 is larger and is returned as the value of left to compare to the value of right = 32 on the previous level of recursion.

 

Part 2:  Mr. Spock's dilemma

 

You are to complete the implemention of Mr. Spock's algorithm for counting the number of ways in which k planets can be selected to visit in a solar system containing n planets (where n >= k).  You are to write the following method inside the Lab3 class:

 

      public static int countCombinations(int n, int k) {...}
   

 

Method countCombinations() must be recursive. This algorithm is given in chapter 3, and it's also provided under the textbook code for chapter 3. Feel free to copy/paste the code to get you started (but remember to change the method name from c() to countCombinations()).
 
Modify the code inside the method such that, before returning a value for the base cases or for the sum of the recursive calls, you print a statement that displays the values in the activation record for each recursive call, as shown here:

 

      System.out.println("n = " + n + ", k = " + k + 

                      ", return value = " + ?); 

    

Note 1: The ? at the end of the println statement indicates where you will replace the ? with either a 1 for the base cases, or with the value returned by the sum of the two recursive calls in the recursive case.

   

Note 2: In the recursive case, the println statement will need to occur after the recursive calls, but before you return from the current call. 

You will need to save the value returned from the sum of the two recursive calls in a temporary variable, then use its contents to first complete the println statement and then to return.

    

Run your program with the values 8 and 5 initially. 

   

Sample Output

 

Here is some sample output: (try to make your output look just like this)

 

> Lab3.countCombinations(8,5);

n = 3, k = 0, return = 1
n = 2, k = 0, return = 1
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 3, k = 1, return = 3
n = 4, k = 1, return = 4
n = 2, k = 0, return = 1
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 3, k = 1, return = 3
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 4, k = 2, return = 6
n = 5, k = 2, return = 10
n = 2, k = 0, return = 1
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 3, k = 1, return = 3
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 4, k = 2, return = 6
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 3, k = 3, return = 1
n = 4, k = 3, return = 4
n = 5, k = 3, return = 10
n = 6, k = 3, return = 20
n = 2, k = 0, return = 1
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 3, k = 1, return = 3
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 4, k = 2, return = 6
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 3, k = 3, return = 1
n = 4, k = 3, return = 4
n = 5, k = 3, return = 10
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 3, k = 3, return = 1
n = 4, k = 3, return = 4
n = 4, k = 4, return = 1
n = 5, k = 4, return = 5
n = 6, k = 4, return = 15
n = 7, k = 4, return = 35
n = 2, k = 0, return = 1
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 3, k = 1, return = 3
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 4, k = 2, return = 6
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 3, k = 3, return = 1
n = 4, k = 3, return = 4
n = 5, k = 3, return = 10
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 3, k = 3, return = 1
n = 4, k = 3, return = 4
n = 4, k = 4, return = 1
n = 5, k = 4, return = 5
n = 6, k = 4, return = 15
n = 1, k = 0, return = 1
n = 1, k = 1, return = 1
n = 2, k = 1, return = 2
n = 2, k = 2, return = 1
n = 3, k = 2, return = 3
n = 3, k = 3, return = 1
n = 4, k = 3, return = 4
n = 4, k = 4, return = 1
n = 5, k = 4, return = 5
n = 5, k = 5, return = 1
n = 6, k = 5, return = 6
n = 7, k = 5, return = 21
n = 8, k = 5, return = 56

    

Submitting your work

     Submit your L3 folder when you are done. It should contain the file Lab3.java.

Log out

Be sure to log out when you are done.