Assignment 2

The Assignment

http://www2.hawaii.edu/~tp_250/ICS211/Fall03/hw02.htm

Comments

You only need one class for this assignment. Please name your file Recursive.java. Please name your 6 methods as follows:

• rFactorial(int)
• iFactorial(int)
• rChoose(int n, int k)
  [where n is the complete set, and k is the number of items to choose from n]
• iChoose(int n, int k)
  [Hint: c(n,k) = n!/((n-k)!*k!)]
• rBinarySearch(int[], int)
• iBinarySearch(int[], int)

Of course, methods beginning with r are recursive forms, and those beginning with i are iterative (or at least non-recursive). You may create a second binarySearch method that takes extra parameters in order to pass the first and last arguments. Similarily, if you don't want to change the names of any methods you've already writen, just include these to call your methods.

You should test the efficiency between the 3 pairs of methods. I suggest you do this in the main() method of Recursive, and report your findings in /* comments */ in your Recursive.java file. But, if you prefer, you can instead write how you tested your methods and your findings in a separate text file.

11 Sept 03: Normally when you test recursive verses iterative functions, you give each version the same very large input and see which takes longer to return an answer. With this particular assignment, you run into problems doing that, since the factorials quickly overflow the datatype. (You can use the java class BigInterger to get around this if you want to.) Instead of using big input, you can use normal input and just run the method many times. Timing the method also helps. For example:

System.out.print("1 million rFactorial(14) calls takes: ");
milliTime1 = System.currentTimeMillis();
for (int i = 0; i <= 1000000; i++){
   recur.rFactorial(14);
}
milliTime2 = System.currentTimeMillis();
System.out.println(milliTime2 - milliTime1);


Grading

This assignment will be out of 10 points. You will get points for the following:

3 - Your program compiles without error

1.5 - Good documentation

See this note on documenting your code.

0.5 - Follows ICS coding standards

Use descriptive variable names, use internal capitalization for names, consistently indent and space code, etc.

3 - 6 methods.

Each of the 6 methods requested exists and works correctly.

0.5 - Correctly named

You followed the naming conventions I've laid out above.

1.5 - Tested

You either describe your tests of the methods or include the code you used to test them. Explain which is more efficient--iterative or recursive--for each of the 3 pairs.