This is an open book, open notes, and open computer test. If you get stuck, talk to Jeff Ondich, but please don't talk to anyone else (not even Justin Thomson or the lab assistants) about the exam.

1. (8 points) Numbers.
   • What is the base-ten equivalent of the 32-bit two's complement number 1111 1111 1111 1111 1111 1111 1010 1100? (The spaces are there just to make it easier to read.)

   • If you run the program factorial.cpp, you will get a listing of purported values of N!, for N ranging from 2 to 20. The numbers look good up to 12, but the value for 13!, listed as 1932053504, is incorrect (the correct value is 6227020800). Explain why the factorials for 13 and beyond are incorrect, and why 13! is listed as 1932053504 in particular.
   
   
   
2. (10 points) Consider the function with prototype "double Sum( double a[], int N )", whose job is to return the sum of the first N elements of a (that is, a[0] + a[1] + ... + a[N-1]).
   • Write an iterative version of Sum.

   • Write a recursive version of Sum. (Hint: computing the sum of the first N elements of a is the same as adding a[N-1] to the sum of the first N-1 elements of a.)
   
   
   
3. (10 points) Elmo has a problem to solve. Given two sorted arrays of N strings each, he wants to know whether the two arrays have any strings in common. So he writes the following function:

   
   	bool HaveCommonElement( string a[], string b[], int N )
   	{
   		bool result = false;
   		for( int i=0; i < N; i++ )
   		{
   			for( int j=0; j < N; j++ )
   			{
   				if( b[i] == a[j] )
   					result = true;
   			}
   		}
   
   		return( result );
   	}
   

   • Suppose Elmo's function takes 2.5 seconds to run when N is 5000. How long does it take when N is 20000? Why?

   • Zoe takes one look at Elmo's code, snorts, and says "Your code works, Elmo, but it's stupid. I can write a function that does it in a tiny fraction of your pathetic time." Though she's being a bit harsh, Zoe's right about Elmo's code. While Big Bird discusses hurt feelings with Zoe and Elmo, you should write a version of HaveCommonElement that beats Elmo's time. (There's a small improvement to Elmo's code that is worth partial credit, and a complete rewrite that is worth full credit.)
   
   
   
4. (12 points) In this problem, you will use sorts.cpp 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.
   
   

   • 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
     1000	?	?	?	?	?	?
     10000	?	?	?	?	?	?
     20000	?	?	?	?	?	?
     30000	?	?	?	?	?	?

   • Describe any patterns you see in the data you collected to fill in the chart above.

   • 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?

   • 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?
   
   
   
5. (6 points) The following function is trying to add the linked list pointed to by secondList onto the end of the list pointed to by firstList (that's what "concatenate" means--to put two or more things end-to-end).

   
   	void Concatenate( Node *firstList, Node *secondList )
   	{
   		// Run to the end of the first list.
   
   		Node *current = firstList;
   		while( current != NULL )
   			current = current->next;
   
   
   		// Link the last node of the first list
   		// to the first node of the second list.
   
   		current->next = secondList;
   	}
   

   Unfortunately, this version of Concatenate doesn't work. Why not? How can you fix it?