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.

1. (a) O( N^3 ) because of three nested loops, and each get is constant time
   (b) O( N^4 ) because the calls to get are O(N)
   (c) For a cubic algorithm, when N is increased
       by a factor of 3, the running time increases
       by a factor of 3^3 = 27. So the time will be 54 sec.
   (d) After the mergesort, the third (innermost loop) can be replaced
       by a binary search for the sum  of the ith and jth element.
       The binary search is O( log N ), so the running time becomes
       O( N^2 log N ) (the cost of the mergesort is less than that).


2. (a) toString is O( N ), removeFirst and addLast are O( 1 )

   (b)
       public String toString( )
       {
           StringBuffer result = new StringBuffer( "[ " );
           for( Node<AnyType> p = header.next; p != null; p = p.next )
               result.append( p.data + " " );
           result.append( "]" );
           return new String( result );
       }

   (c)
       public boolean removeFirst( )
       {
           if( last == null )
               return false;  // or throw an exception

           if( header.next == last )
               header.next = last = null;
           else
           {
               header.next = header.next.next;
               header.next.previous = header;
           }

           return true;
       }

   (d)
       public void addLast( AnyType x )
       {
           if( last == null )
               header.next = last = new Node<AnyType>( x, header, null );
           else
               last = last.next = new Node<AnyType>( x, last, null );
       }



3.
   (a)
     public static List<String> sumsToTen( Map<String,List<Integer>> m )
     {
         List<String> result = new ArrayList<String>( );

         for( Map.Entry<String,List<Integer>> e : m.entrySet( ) )
         {
             List<Integer> nums = e.getValue( );
             int sum = 0;

             for( Integer x : nums )
                 sum += x;                /* 1 */

             if( sum == 10 )
                 result.add( e.getKey( ) );
         }

         return result;
     }


   (b) [NOTE: This part was not scored...]
     The running time depends on how we define N. If N is total number
     of items in all the lists, and we assume no list is empty, then the
     running time is O( N ), because that is how many times line /*1*/ is
reached.


4.
    public static int getWaterArea( GridElement pos )
    {
        Collection<GridElement> waterElements = new HashSet<GridElement>( );
        getWaterArea( pos, waterElements );
        return waterElements.size( );
    }

    private static void getWaterArea( GridElement pos, Set<GridElement>
alreadyUsed )
    {
        if( !alreadyUsed.contains( pos ) && pos.containsWater( ) )
        {
            alreadyUsed.add( pos );

            for( GridElement g : pos.getAdjacent( ) )
                getWaterArea( g, alreadyUsed );
        }
    }