Hand in on paper.

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. There are a lot of words in this test, so it's likely you will find some ambiguity. If you have questions, ask them. It's not noble to suffer needlessly.

1. (10 points) Write a recursive procedure that prints out the lyrics of "N Bottles of Beer on the Wall" (see the first midterm for a description of this song).

2. (The longest 5-point question in history) If you define a record type in Pascal, variables of that type can be assigned to one another. For example, to sort the person records on the last programming assignment, most of you wrote something like this:

   
       procedure Sort( var mypeople : personArray; nPeople : integer );
       var         temp : person;
       begin
                .
                .
                .
                temp := mypeople[indexOfMax];
                mypeople[indexOfMax] := mypeople[j];
                mypeople[j] := temp;
                .
                .
                .
       end;
   

   That is, even though Pascal doesn't have the person type built in to it, the compiler can arrange for the program to copy one person record to another, simply by copying the record one byte at a time. That's nice, and helps make thinking abstractly using records easy.

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

   
       if  temp = mypeople[k] then
           DoSomething
       else
           DoSomethingElse;
   

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

   (Here's a hint. Think about our person records. When will we consider two person records "equal"? Must all of their bytes be exactly equal?)

3. (5 points) Does the following code ever stop running? If so, what output does it produce and why? If not, why not? Assume that i has been declared an integer.

   
       i := 1;
       while i > 0 do
           i := i + 1;
   
       writeln( i );
   

   If you're interested, gpc integers take up four bytes.

4. (10 points for either one, 15 points for both) In the last few days, we have used linked lists to implement character strings. A character string in this context is a linked list of nodes described by the following type definitions.

        type nodePtr = ^node;
   
             node = record
                  data : char;
                  next : nodePtr
             end;
   

   For this problem, you will write a function and a procedure to manipulate such character strings.

   1. Write a function that takes a character and a string as parameters, and returns true if the given character is in the given string at least once, and false otherwise. Use the following prototype.

       
           function IsCharInString( c : char; s : nodePtr ) : boolean;
       

   2. Write a procedure that takes a character and a string as parameters, and adds the character to the end of the string. Use the following prototype.

       
           procedure AddCharToString( c : char; var s : nodePtr );
       

   Make sure to say whether you are assuming the character strings to be stored forwards or backwards in their linked lists (i.e. whether "bug" is stored as head->b->u->g->nil or as head->g->u->b->nil).

5. (4 points) Tell me your favorite joke.

6. (15 points) The Selection Sort algorithm has a loop inside a loop.

   
       for i := 1 to N-1 do
       begin
           indexOfMax := i;
           for j := i + 1 to N do
           begin
               if a[indexOfMax] < a[j] then
                   indexOfMax := j;
           end;
   
           temp := a[indexOfMax];
           a[indexOfMax] := a[i];
           a[i] := temp
       end
   

   When we analyzed the time complexity of Selection Sort, it became clear that the vast majority of the execution time was spent inside this inner loop, especially when the number of items we were sorting (N) was large. More specifically, the number of times j gets incremented or a[indexOfMax] gets compared to a[j] is much larger than the number of times i gets incremented or temp gets changed. Thus, the number of times the body of the inner loop gets executed gives a good indication of the amount of time this algorithm will take to execute.

   Consider now the Merge Sort algorithm in mergesort.p. This recursive algorithm is convoluted enough that it is not immediately obvious where the bulk of the computation time is being spent. In this problem, you're going to investigate this matter to determine whether Merge Sort might offer an improvement over Selection Sort.

   I have written the main program of mergesort.p to allow you to sort arrays of more or less any length you specify. Try running the program a couple of times with different input to see it work.

   Now it's time to get down to work. First of all, it is possible that most of the time spent in Merge Sort is spent just calling procedures. Thus, we'll want to know how many times Merge() and MergeSort() are called for various values of N, and whether there's a pattern to these numbers.

   On the other hand, it's possible that the bulk of the execution time takes place inside Merge(), which is a relatively complicated procedure. Once you get to know this procedure, you will agree that the number of operations performed by Merge() is approximately proportional to the "width" of the interval from bottom to top (that is, bottom - top + 1). Thus, Merge() will take about twice as long to do its work if the width is 1000 than if it is 500, and so on. Thus, we'll want to know the sum of all the widths Merge() gets called with during execution of the overall MergeSort() algorithm.

   Here's what I want you to do. Modify the mergesort.p program to report to you the number of times Merge() gets called, the number of times MergeSort() gets called, and the sum of all the widths in all the calls to Merge(). Try this modified program out for a variety of values of N (I recommend powers of 2 for N to make some of the patterns that arise easier to see). Collect enough data in a table like the one below so you can see patterns forming. While you're at it, collect similar data for Selection Sort.

                       M  E  R  G  E     S  O  R  T               Selection Sort
                # times           # times            total         # times body
               MergeSort()        Merge()         widths that      of inner loop
       N       gets called      gets called       get merged       gets executed 
   -----------------------------------------------------------------------------
      16           ??               ??                ??                ??
      32           ??               ??                ??                ??
      64           ??               ??                ??                ??
     etc.
   

   Can you give me a formula for each of the four columns of this table in terms of N? When N gets really large, which column dominates the execution time for Merge Sort? Which sorting algorithm would you expect to be faster for large N, or is there no noticeable difference?

   Finally, have a race between Merge Sort and Selection Sort on an array of, say, 10000 integers. Which one wins? By how much?