Midterm Answers



1.
   (a) O(N^2).
   (b) 16 seconds (2^2 times as fast).
   (c) Sort the array; after that for each item a[i],
       search for K-a[i] by a binary search.
       Sort is O(N log N), with an efficient sort.
       N calls to binary search (each call is O(log N))
       total O(N log N). So total time is O(N log N).


2.
   int Balance( Node *T )
   {
       if( T == NULL || ( T->Left == NULL && T->Right == NULL )
           return 0;
       else if( T->Right == NULL )      // Left child only
           return 1 + Balance( T->Left );
       else if( T->Left == NULL )      // Right child only
           return -1 + Balance( T->Right );
       else                             // Two children
           return Balance( T->Left ) + Balance( T->Right );
   }

   (b) The running time is O(N).


3.
   template <class Object>
   void SplitList( const list<Object> & theList, list<Object> & evens,
                                                 list<Object> & odds )
   {
       list<Object>::const_iterator itr;

         // Alias test
       EXCEPTION( &theList == &evens || &theList == &odds || &evens == &odds,
                  "Two or more lists are aliased" );

         // Make outputs empty
       while( !evens.empty( ) )
           evens.pop_front( );
       while( !odds.empty( ) )
           odds.pop_front( );

       int position = 1;
       for( itr = theList.begin( ); itr != theList.end( ); itr++ )
           if( position++ % 2 == 0 )     // even position
               evens.push_back( *itr );
           else
               odds.push_front( *itr );
   }
 
           
4.
   A complete implementation is in the text, or online as QueueLi.h and .cpp.
   I accepted solutions that disabled operator=.