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^2 )
   (b) O( N^3 ) because calls to get are expensive
   (c) For a quadratic algorithm, when N is increased
       by a factor of 3, the running time increases
       by a factor of 3^2 = 9. So the time will be 36 sec.
       there are at most N, so the total is O( N log N ).
   (d) Using the iterator will not significantly affect the performance
       when the list is an ArrayList, but for LinkedList's, it
       reduces the running time to O( N^2 ) by avoiding the
       expensive calls to get.


2. (a) toString is O( N ), removeLast and addFirst 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 removeLast( )
       {
           if( last == null )
               return false;  // or throw an exception

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

           return true;
       }

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



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

         for( Map.Entry<String,List<Integer>> e : m.entrySet( ) )
         {
             String word = e.getKey( );
             List<Integer> lines = e.getValue( );

             for( Integer line : lines )
             {
                 List<String> strs = result.get( line );
                 if( strs == null )
                 {
                     strs = new ArrayList<String>( );
                     result.put( line, strs );
                 }
                 strs.add( word );
             }
         }

         return result;
     }


   (b)
     The running time depends on how we define N. If N is the sum total
     of occurrences of all words then the running time is
     O( N log N ) since each occurrence incurs a fixed number of
     TreeMap operations that cost at most O( log N ) each.

     If N is the number of words and N is also the number of lines,
     then that means there is roughly N^2 in terms of input, and
     O( log (N^2) ) = O( log N ) for each TreeMap operation, which
     yields O( N^2 log N ) as the running time.

     Other more involved calculations use N as the number of words
     and M as the number of lines and yield O( NM log (NM) ) as the
     running time.

4.
     public static Set<String> getAllWords( String word )
     {
         Set<String> result = new TreeSet<String>( );

         if( word.equals( "" ) )
              result.add( "" );
         else
         {
              Set<String> subResult = getAllWords( word.substring( 1 ) );
              for( String s : subResult )
              {
                   result.add( s );
                   result.add( word.charAt( 0 ) + s );
              }
         }

         return result;
     }