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) The following method sorts an array of integers in increasing order. Show the changes you would make to cause this method to sort an array of real numbers in decreasing order.

   
   public static void sort( int[] a )
   {
   	int	j, k;
   	int	temp;
   
   	for( j=1; j < a.length; j++ )
   	{
   		temp = a[j];
   		for( k=j-1; k >= 0  &&  temp < a[k]; k-- )
   			a[k+1] = a[k];
   		a[k+1] = temp;
   	}
   }
   

2. (5 points) The BlueJ project S:/Shared_Faculty_Files/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.

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

4. (8 points) I have an array a[] of integers, and I want to know the distance between the pair of these numbers that are furthest apart. Elmo suggests the following code, which does the job:

   
   public static int elmo( int[] a )
   {
   	int max = 0;
   	for( int i=0; i < a.length; i++ )
   	{
   		for( int j=0; j < a.length; j++ )
   		{
   			if( a[i] - a[j] > max )
   				max = a[i] - a[j];
   		}
   	}
   }
   

   • When I used Elmo's code on an array of 2000 integers on my slow old computer at home, it took 8.0 seconds (I tried it several times--8.0 seconds every time). Approximately how long will Elmo's code take to run if N = 6000 (assuming I use the same computer)? Justify your answer. (It is not sufficient to tell me that you ran the code yourself and it took a certain amount of time. I want you to explain why it will take as long as you say it will.)
   • Zoe says she thinks Elmo's code is stupid. Describe an algorithm that will run significantly faster than Elmo's, and explain why it's faster.

5. (8 points) Write a static recursive method that takes an integer N as a parameter and returns the sum of the first N squares.

6. (8 points) Look at the BlueJ project in S:/Shared_Faculty_Files/Ondich/int_lists. This is the same as the lists project that I demonstrated in class Wednesday, 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 return the sum of the data. For your convenience, I have provided you with a stub of the sum method in IntList, and I have put testing code into the main method in IntListTester.

7. (8 points) Write a paragraph or two describing what you plan to do for your final project. After your description, provide me with your incremental development plan--that is, a list of baby 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.