Midterm Answers

(In these solutions, ^ means exponentiation)


1. (a) O(N^3).
   (b) 640 seconds (4^3 times as long).
   (c) Sort the array; after that all triplicates will
        be in three consecutive array positions and can be
        found in a linear-time sequential scan.
        Running time is O(N log N), with an efficient sort.

2. See any of the queue implementations online.

3. (a)

       template <class Etype>
       void
       Reverse( const List<Etype> & Input, List<Etype> & Output )
       {
           Stack<Etype> Items;

           for( ListItr<Etype> Itr = Input; +Itr; ++Itr )
               Items.Push( Itr( ) );

           Output.MakeEmpty( );
           ListItr<Etype> OutItr = Output;
 
           while( !Items.IsEmpty( ) )
               OutItr.Insert( Items.TopAndPop( ) );
       }

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

4. (a) The total cost is O( N log N ) on average and
        O( N^2 ) worst-case, because there are N inserts at
        O( log N ) average cost and/or  O( N ) worst-case cost.

   (b) Insertion sort is O( N^2 ) in both cases.
       Mergesort is O( N log N ) in both cases.
       Quicksort is O( N log N ) on average, O( N^2 )
        in the worst case. The worst case occurs
        when the partition is repeadtly degenerate.