For this exam, you may use your textbook, your computer, the Internet, the library, and divine guidance (if any is available to you). You may not, however, discuss this exam with any person other than Jeff Ondich. You are welcome to ask Jeff questions, and he will decide whether to answer them.

1. (6 points) Consider the following method.

   public static int Something( int[] a, int N )
   {
   	if( N == 1 )
   		return a[0];
   	else
   	{
   		int k = Something( a, N - 1 );
   		if( a[N-1] > k )
   			return a[N-1];
   		else
   			return k;
   	}
   }
   

   • What task does Something accomplish?
   • Change the names of Something and k to names that are more descriptive.
   • It's possible to pass Something parameters that would cause it to crash your program. Explain.

2. (6 points) Consider the following method.

   public static int factorial( int N )
   {
   	int result = 1;
   	for( int k=2; k <= N; k++ )
   		result = result * k;
   
   	return result;
   }
   

   • What is the actual value of 13 factorial?
   • What value does factorial(13) return?
   • Why does factorial(13) return an incorrect value? More specifically, Why does factorial(13) return this particular incorrect value?

3. (9 points) The following method is a buggy binary search. Your job is to:

   • give an example that demonstrates the failure of this method,
   • explain the nature of the failure, and
   • explain how to fix the problem.

   // Returns the index where searchKey is found in the array,
   // or -1 if searchKey is not in the array.  (At least, that's
   // what it would do if it weren't buggy.)
   //
   // Precondition: the array a is sorted in increasing order.
   
   public static int binary_search( int searchKey, int[] a )
   {
   	int	left = 0;
   	int right = a.length - 1;
   	int middle;
   
   	while( left <= right )
   	{
   		middle = (left + right) / 2;
   		if( a[middle] == searchKey )
   			return middle;
   
   		else if( a[middle] < searchKey )
   			left = middle;
   
   		else
   			right = middle;
   	}
   
   	return -1;
   }
   

4. (7 points) The BlueJ project /Accounts/courses/cs117/ondich/swaps shows attempts to write methods that will swap two integers, two instances of class Thing, and two elements of an array of integers. Which of these swap methods work, and which do not? Explain why.

5. (2 points) I'm all out of jokes. If you have a good one, please tell it to me.

6. (7 points) Write a static recursive method that takes a string s as a parameter and returns the number of upper-case letters in s.

7. (7 points) Look at the BlueJ project in /Accounts/courses/cs117/ondich/int_lists. This is the same as the lists project that I demonstrated in class Monday, except for the fact that the nodes in int_lists contain integer data instead of character data. Your job is to add a method to the IntList class that will determine whether the list is sorted in increasing order (that is, the first number is the smallest, the second is next smallest, etc.). For your convenience, I have provided you with a stub of the isIncreasing method in IntList, and I have put testing code into the main method in IntListTester.

8. (10 points) Write a brief description of what you plan to do for your final project. After your description, provide me with your incremental development plan--that is, a list of small steps that will take you from no program at all to a completed project. Each step should be testable independently of the others, so you can run a loop like this:

   • Complete a step on the incremental development plan list.
   • Compile the program.
   • Test the program to make sure your new additions work, and that they didn't break previously completed features.
   • SAVE A COPY OF THE WORKING CODE AND NEVER TOUCH IT AGAIN.
   • Repeat.

   One of the lovely things about a good incremental development plan is that you can stop after any iteration of this loop and you will have a functioning program. It might not do everything you want it to do, but it compiles and it runs.