Midterm Answers



1.
   (a) O(N^2).
   (b) Clearly computer B solves the 100,000 element problem in 1 sec.
       Since we have a quadratic algorithm, 4 times the input implies
       4^2 the running time, so in 16 sec. computer B can solve a
       400,000 element problem.
   (c) There are O(N) find and insert operations at O(log N) cost
       per operation, so the total is O(N log N).


2.
   template <class Comparable>
   Comparable mostFrequent( const vector<Comparable> & v )
   {
       map<Comparable,int> m;

       for( int i = 0; i < v.size( ); i++ )
           m[ v[i] ]++;

       map<Comparable,int>::iterator itr, max;

       max = itr = m.begin( );
       for( itr++; itr != m.end( ); itr++ )
           if( (*itr).second > (*max).second )
               max = itr;

       return (*max).first;
    }


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

         // Alias test
       if( &theList == &evens || &theList == &odds || &evens == &odds )
           throw AliasException( );   // assume this class exists

         // 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.
   iv, ii, iv, i, iv