Here is a quick sketch of the solutions.
In grading, I am looking only for a few things on each question,
and an overall understanding of the important concepts.

VERSION A

1.
(a) String concatenation takes time that is linear in the size
    of the String. So the total cost is approximately
         1 + 2 + 3 + ... + N
    which is O( N^2 ).

(b) For an O( N^2 ) algorithm, triple the input means 9 (3*3) times
    as long to run. So, it takes 72 milliseconds.
    (If you answered O( N ) for part (a), you got full credit for
     24 milliseconds.)

(c) The rewrite uses a StringBuffer to get a linear-time algorithm.

  public static String toString( Object [ ] arr )
  {
      StringBuffer sb = new StringBuffer( "[" );

      for( int i = 0; i < arr.length; i++ )
          sb.append( " " + arr[ i ] );
      sb.append( " ]" );

      return new String( sb );
  }
       
2.
(a)
  // Runs in O(N) time
  public boolean contains( Object x )
  {
      for( Node p = beginMarker.next; p != endMarker; p = p.next )
          if( p.data.equals( x ) )
              return true;

      return false;
  }

(b)
  public void remove( Node p )
  {
      p.next.prev = p.prev;
      p.prev.next = p.next;
  }

(c)
  public void removeLast( )
  {
      if( isEmpty( ) )
          throw new NoSuchElementException( );

      remove( endMarker.prev );
  }

3.
  public static void removeSomeEntries( Map m )
  {
      Set entries = m.entrySet( );
      Iterator itr = entries.iterator( );

      while( itr.hasNext( ) )
      {
          Map.Entry e = (Map.Entry) itr.next( );
          if( e.getKey( ).equals( e.getValue( ) ) )
              itr.remove( );
      }
  }

  Note: you cannot use the Map or Set's remove method, since
  it will invalidate the iterator.

4.
  public static void mergesort( Object [ ] arr, Comparator cmp )
  {
      mergeSort( arr, cmp, 0, arr.length - 1 );
  }

  private static void mergeSort( Object [ ] arr, Comparator cmp, int low, int
high )
  {
      if( low <  high )
      {
          int mid = ( low + high ) / 2;

          mergesort( arr, cmp, low, mid );
          mergesort( arr, cmp, mid + 1, high );

          merge( arr, cmp, low, high );
      }
  }