This is an open book, open notes, and open computer test. You may not use any books other than your textbook, and you may not use Internet resources from off campus. If you get stuck, talk to Jeff Ondich, but please don't talk to anyone else about the exam.

1. (5 points) What output, if any, does the following code produce? Why?

   
   	short	i = 1;
   	while( i > 0 )
   	{
   		i++;
   	}
   	cout << i << endl;
   

   
   
   
2. (10 points) Write a recursive function that computes the sum of the integers between 1 and N. Use the following prototype.

   
   	int Sum( int N );
   

   
   
   
3. (10 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];
   		}
   	}
   

   1. When I used Elmo's code on N = 5000 numbers, the program took 1.5 seconds (I tried it several times--1.5 seconds every time). 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.)
   2. 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.
   
   
   
4. (5 points) The following function accepts a linked list as input. What does this function do? (Stated a different way, what is the meaning of the return value?)

   
   
   	struct CharNode
   	{
   		char		mData;
   		CharNode	*mNext;
   	};
   	typedef 	CharNode *		CharNodePtr;
   
   	int MysteryFunction( CharNodePtr& head )
   	{
   		int		n = 0;
   		CharNodePtr		current = head;
   		while( current != 0 )
   		{
   			n++;
   			current = current->mNext;
   		}
   		return( n );
   	}	
   

   
   
   
5. (2 points) Please tell me a joke.
   
   
6. (12 points) I have added a sorting algorithm called Merge Sort to the sorts.cpp program that we have looked at in class. This problem will give you a chance to compare the performance of Selection Sort, Insertion Sort, and Merge Sort.

   Selection, Insertion, and Merge Sorts are all members of a class of sorting algorithms whose performance is usually measured by counting the number of array element comparisons need to be done to complete the sorting of the array. That is, we count the number of times something like "if( a[i] < a[j] )" gets executed during the run of the algorithm. It would take several pages to provide a reasonably rigorous argument that the comparison count is a good measure of performance for these algorithms. With a lot less rigor, we can say something like this: by counting comparisons, we are counting the number of iterations of the inner loop, and by counting inner loop iterations, we are counting the most time-consuming portion of the algorithm.

   So, in what follows, you're going to count comparisons and measure running times for the three algorithms and several values of N. Let's get started.
   
   

   1. Fill in the following chart.

      N	Comp. count for Sel. Sort	Running time for Sel. Sort	Comp. count for Ins. Sort	Running time for Ins. Sort	Comp. count for Merge Sort	Running time for Merge Sort
      10	?	?	?	?	?	?
      100	?	?	?	?	?	?
      1000	?	?	?	?	?	?
      10000	?	?	?	?	?	?
      20000	?	?	?	?	?	?
      30000	?	?	?	?	?	?

   2. Describe any patterns you see in the data you collected to fill in the chart above.
   3. Is the comparison count for Selection Sort dependent on the initial data? (For example, if you run Selection Sort several different times on different randomly generated arrays of 10000 items, is the comparison count the same every time?) How about Insertion Sort? Merge Sort?
   4. Under what conditions would you choose to use Merge Sort instead of Insertion Sort and Selection Sort? When would you choose Insertion Sort? When would you choose Selection Sort?