Midterm Answers

(In these solutions, ^ means exponentiation)


1. (a) O(N^2).
   (b) 160 seconds (4^2 times as long).
   (c) Sort the two arrays separately; after that, use the scanning
       algorithm from the "merge" step in mergesort, but add a test to
       see if two equal elements are being scanned.
       Running time is O(N log N), with an efficient sort.

2. See any of the stack implementations online.
   Pay particular attention to constness, error-handling, actual C++ code
   versus fake code, missing semicolons, etc.

3. (a) Use the same idea as the quicksort partitioning scheme, and
       have counters i and j run from the ends of the array towards
       each other, swapping out-of-place items.
       
   (b)
       // Need the i < j test in case all items are good or all are bad
       // There are many variations on the code below; this is simplest.
       void Rearrange( Vector<Object> & A )
       {
           for( int i = 0, j = A.Length( ) -1; ; )
           {
               while( i < j && A[ i ].IsGood( ) )
                   i++;
               while( i < j && !A[ j ].IsGood( ) )
                   j--;
               if( i < j )
                   Swap( A[ i ], A[ j ] );
               else
                   break;
           }
       }
               
4. (a) The last operation is O( log N ) on average and
        O( N ) worst-case.

   (b) (i)    Mergesort (the only one with an O( N log N ) guarantee).
       (ii)   Insertion sort (the only one with O( N^2 ) average case).
       (iii)  Insertion sort. Shellsort is also possible, depending
              on the implementation. Quicksort uses extra space because
              of the stack for recursion, and thus is incorrect.
       (iv)   Insertion sort and shellsort.
       (v)    Insertion sort (the only one that is O( N ) in this case).