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.

Provide brief, clear justification for your answers.

This exam has a time limit, of sorts. You may think about it all you like, with or without paper and textbook at hand. But don't use more than 5 hours combined working at the computer and writing up your answers.

1. (8 points) What output does the following code produce? Why?

   
   	short k = -32768;
   	k = k * -1;
   	cout << k << endl;
   

2. (15 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.

3. (15 points) The program sierpinski.cpp draws a picture. Try it out, and then answer the following questions.
   • Draw a diagram of the triangle drawn by DrawTriangle, with the coordinates and lengths right, bottom, and legLength clearly labeled.

   • What is the meaning of the depth parameter in DrawPicture, in geometrical terms?

   • If howDeep is 1, how many triangles get drawn? What if howDeep is 2? 3? 4?

   • If howDeep is 3, which triangles get drawn first, second, third, fourth, and last (you can draw a diagram and label it)? Why?

   • Write a formula for the number of triangles drawn, assuming that howDeep is N.

   • If you move the line labeled "LINE A" to the location "LINE B", how is the drawing process changed?

4. (3 points) I would be much obliged if you would recommend a book for me to read.

5. (12 points) Consider the weird little program sesame.cpp.
   • If you run the program as it is, which functions get called, and in which order? Why?

   • If you uncomment LINE A, but leave LINE B commented out, which functions get called, and in which order? Why?

   • If you uncomment LINE B, but comment out LINE A, which functions get called, and in which order? Why?

   • If you have not already done so, explain clearly why the previous two answers are different.

6. (The longest 5-point question in history) Suppose you define the following struct:

   
   const int maxNameLength = 50;
   
   struct Person
   {
   	char		name[maxNameLength+1];
   	int			heightInInches;
   	int			numberOfPets;
   
   	// More stuff if you feel like it.
   };
   

   C++ allows you to assign one Person variable to another. For example, to sort a collection of Person structs, you might use code like this:

   
   void SelectionSort( Person p[], int nPeople )
   {
   	...
   
   		Person temp;
   		
   		temp = p[indexOfMax];
   		p[indexOfMax] = p[i];
   		p[i] = temp;
   
   	...
   }
   

   That is, even though C++ doesn't have the Person type built in to it, the compiler can arrange for the program to copy one Person variable to another, simply by copying the struct one byte at a time. That's nice, and helps make thinking abstractly using structs and classes easy.

   Here's the weird thing. You can't compare structs like this:

   
   	Person	a, b;
   
   	...
   
   	if( a == b )
   	{
   		// Do something
   	}
   	else
   	{
   		// Do something else
   	}
   

   This code simply won't compile. But why not? If the C++ compiler is happy to let you copy one struct to another, byte for byte, why won't it let you compare two structs with one another, byte for byte? For what reason would the designers of the C++ language want to avoid letting you test two records for equality in this way?