This is an open-book, open-computer exam. You may use your textbook, your notes, your programs, and whatever information you find on the course Web page. You may not consult other books or on-line resources. Do not discuss this exam with people other than Jeff Ondich, who will be glad to answer your questions if he feels it appropriate to do so. If you have questions, ask them. It's not noble to suffer needlessly.

Please submit your exam on paper.

Stay cool, and have fun.

1. (10 points) Numbers and characters.
   • What is the base ten expression of the 16-bit two's complement integer 1111 1111 1101 1010? (I have put spaces in this number to make it easier to read. That really is one 16-bit number, not four 4-bit numbers.)
   • What is the 16-bit two's complement expression of the base ten integer 29?
   • What output does the following code fragment produce? Explain why. You may assume that ch has been declared to have type char.

     
            ch := 'B';
            ch := chr( ord(ch) - 3 );
     	   writeln( ch );
     

2. (10 points) The program liststrings.p contains several procedures for manipulating linked lists of characters. Write a non-recursive function

   
         function StringLength( str : nodePtr ) : integer;
   

   to return the number of character nodes in the linked list pointed to by str.

3. (10 points) Write a recursive version of StringLength from the previous problem.

4. (3 points) Tell me a joke, please.

5. (15 points) This problem uses the program midtermsort.p.
   • If you compile and run midtermsort.p as is, it will generate a random shuffling of the integers 1 through 10, sort those numbers, and quit without producing any output. If you remove the comment braces on the lines labeled ****, the resulting program will print out the contents of the array before sorting begins, and after each pass of the selection sort algorithm. Try running the program this way.

     Now, explain in one or two sentences the strategy employed by the selection sort algorithm. (The output in the previous step may tell you what you need to know, but you might want to take a look at the code for SelectionSort all the same.)

     Finally, give a formula in terms of the parameter N for the number of times the comparison num[j] < num[indexOfMin] is performed when you run SelectionSort.

   • Next, comment out all calls to PrintList, and set the constant maxIntarraySize to 1000. Recompile and then time the program using the Unix command time midtermsort. The timing number you want to record is the far left one (something like "3.8u", which means your program spent 3.8 seconds actually computing stuff as opposed to waiting around). Try this a couple of times to make sure you get consistent timing data.

     Time the program for maxIntarraySize equal to 1000, 2000, 3000,...,8000. Are the times you get consistent with what you would expect given the formula you derived in the previous part?

   • Go down to the main program, comment out the call to SelectionSort, and uncomment the call to MergeSort. Set maxIntarraySize back to 10. Make sure the call to PrintList in MergeSort is uncommented so you'll get some output. Run the program this way to see how the array looks after each call to Merge.

     Explain in one or two sentences the strategy employed by the merge sort algorithm.

   • As you did with selection sort, time merge sort for maxIntarraySize equal to 1000, 2000, 3000,...,8000.
   • If you were to derive a formula for the number of operations performed by MergeSort on an N-item array, your formula's highest-order term would be some constant times N*log(N). Based on this information and your timing data, approximately how long would you expect MergeSort to take to sort 1,000,000 items? How long would you expect SelectionSort to take to sort 1,000,000 items?