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.

1. (10 points) Write a recursive function that takes a character, a character array, and an integer N as input, and returns the number of times the character appears in the first N entries of the character array.

2. (5 points) Using gpc on the machines in CMC 306, what do you get if you square an integer variable whose value is 50000? Why?

3. (10 points) 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;
   

   Write a procedure that takes two strings as parameters, and attaches the second string to the first. (The standard CS term for this operation is concatenation.) For example, if the parameters point to strings like this:

    
        firstString -> C -> A -> T -> nil
        secondString -> F -> I -> S -> H -> nil
    

   when StringConcatenate() is called, then after StringConcatenate is done, they will point to strings like this:

    
        firstString -> C -> A -> T -> F -> I -> S -> H -> nil
        secondString -> F -> I -> S -> H -> nil
    

   Use the following prototype.

    
        procedure StringConcatenate( var firstString : nodePtr; secondString : nodePtr );
    

4. (4 points) My son will be turning 6 shortly, and my wife will be 34 a few weeks later. What should I get them for their birthdays?

5. (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, top - bottom + 1). For example, Merge() will take about three times as long to do its work if the width is 1500 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.
   

   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?