Midterm Answers


(In these solutions, ^ means exponentiation)

(Prepared remotely, without a good editor. Sorry for typos).

1. (NIGHT CLASS)
   (a) O(N^3).
   (b) 640 seconds (4^3 times as long).
   (c) Sort the array; after that for each pair a[p], a[q],
       search for K-a[p]-a[q] by a binary search.
       Sort is O(N log N), with an efficient sort.
       O(N^2) calls to binary search (each call is O(log N))
       total O(N^2 log N). So total time is O(N^2 log N).
   (DAY CLASS)
   (a) O(N^2).
   (b) 160 seconds (4^2 times as long).
   (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.

#include <list>
using namespace list;

template <class Object>
class Queue
{
  public:
        // Note: constructors, destructors, op= all acceptable
    bool IsEmpty( ) const;
    void MakeEmpty( );
    void Enqueue( const Object & X );
    void Dequeue( Object & X );
    const Object & GetFront( ) const;

  private:
    list<Object> L;
};

template <class Object>
bool Queue<Object>::IsEmpty( ) const
{
    return L.empty( );
}

template <class Object>
void Queue<Object>::MakeEmpty( ) 
{
    while( !L.empty( ) )
        L.pop_front( );
}

template <class Object>
void Queue<Object>::Enqueue( const Object & X )
{
    L.push_back( X );
}

template <class Object>
void Queue<Object>::Dequeue( Object & X )
{
    if( L.empty( ) )
        throw "Empty queue";
    X = L.front( );
    L.pop_front( );
}

template <class Object>
const Object & Queue<Object>::GetFront( ) const
{
    if( L.empty( ) )
        throw "Empty queue";
    return L.front( );
}



3. (NIGHT CLASS)
   int NumWithTwoChildren( Node *T )
   {
       if( T == NULL )
           return 0;
       int me = ( T->Left != NULL && T->Right != NULL ) ? 1 : 0;
       return me + NumWithTwoChildren( T->Left ) + NumWithTwoChildren( T->Right );
   }

   (DAY CLASS)
   int NumWithOneChild( Node *T )
   {
       if( T == NULL )
           return 0;
       int me = ( T->Left == NULL ) != ( T->Right == NULL ) ? 1 : 0;
       return me + NumWithOneChild( T->Left ) + NumWithOneChild( T->Right );
   }


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

4. (DAY AND NIGHT ARE SIMILAR. I DESCRIBE THE NIGHT VERSION)

   The maximum difference is at least zero (i==j), so that
   can be the initial value of the answer to beat.
   At any point in the algorithm, we have the current value j,
   and the current low point i. If a[j]-a[i] is larger than
   the current best, update the best difference. If a[j] is less
   than a[i], reset the current low point to i.
   Start with i at index 0, j at index 0. j just scans the array,
   so the running time is O(N).

   Alternate O(N log N) solution is to use divide-and-conquer.
   Recursively compute best answer in left half and right half.
   Compute best answer that crosses the center border (via separate
   loops, find the minimum value in the left half and the maximum
   in the the right half; their difference is the best answer that spans the
   center divider). Return the best of the three possibilities.

   For the day class, replace - with / (and + with * for
   recursive solution). Logic is the same,
   except that the initial value to beat is 1.