This is an open book, open notes, and open computer test. If you get stuck, you may talk to me (Jeff Ondich) or Jenny Cooper, but please don't talk to anyone else (including the lab assistants) about the exam.

1. (15 points) Write two versions of the following function, one recursive and one iterative.

   
   	// Returns true if the given character is equal to
   	// a[0] or a[1] or...or a[N-1], and false otherwise.
   
   	bool IsCharInArray( char ch, char a[], int N )
   	{
   		//...
   	}
   

   
   
   
2. (9 points) Modify the main program in emailClassTester.cpp to sort the array of e-mail messages by subject line before printing them out. Hand in your new main program, and any other code you added or changed in emailClassTester.cpp, emailClass.cpp, or emailClass.h.
   
   
3. (9 points) Searching in computer science is the process of looking through a collection of items to find a particular item. For example, the function IsCharInArray in problem 1 is a search function.
   • Read about binary search in your textbook.

   • Suppose you have a list of the US states in alphabetical order, and you want to know whether Saskatchewan is on the list. Start at the beginning of the list and compare Saskatchewan to each item until you find Saskatchewan or encounter an item that is alphabetically later than Saskatchewan. (This is called "linear search on a sorted list.") To how many states do you need to compare Saskatchewan before you determine that it's not on the list? What is the last state to which you compare Saskatchewan?

   • Now do binary search for Saskatchewan. To how many states do you need to compare Saskatchewan before you decide it's not on the list? List the states to which you compare Saskatchewan, in the order in which you do the comparisons.
   
   
   
4. (12 points) I have N numbers stored in an array a[], 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:

   
   	int max = 0;
   	for( int i=0; i < N; i++ )
   	{
   		for( int j=0; j < N; j++ )
   		{
   			if( a[i] - a[j] > max )
   				max = a[i] - a[j];
   		}
   	}
   

   • When I used Elmo's code on N = 5000 numbers, the program took an average of 4.2 seconds (I tried it several times). Approximately how long will Elmo's code take to run if N = 30000 (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. Elmo says, "Elmo likes Elmo's code. If Zoe thinks she can do better, Zoe should show Elmo how." Describe an algorithm that Zoe could use to show Elmo that his code is too slow. Explain why your algorithm faster than Elmo's.
   
   
   
5. (2 points) Tell me a joke, please.
   
   
6. (7 points) A little binary arithmetic.
   • What is the base ten equivalent of the binary number 1000110?

   • What character is represented by the byte 01000110 in ASCII?

   • Suppose you have an int-type variable i, and you want to print out its binary equivalent. How would you do it? (Hint: it's easier to print it backwards than forwards, and you can use the operations / and % to good effect.)