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 )
   (b) O( N^2 ), because each call to remove is O( N ) and there
       are N calls.
   (c) For a quadratic algorithm, when N is increased
       by a factor of 5, the running time increases
       by a factor of 5^2 = 25. So the time will be 100 sec.
   (d) The alternate method uses a Collection remove, and an
       iterator (generated by the enhanced for loop). The iterator
       becomes invalid when the remove is used, so the
       alternate method DOES NOT WORK.


2. (a) toString is O( N ), removeLast and addFirst are  O( 1 )

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

   (c)
       public void removeLast( )
       {
           if( first == null )
               throw new IllegalStateException( );
           if( first == last )
               first = last = null;
           else
           {
               last = last.prev;
               last.next = null;
           }
       }

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



3.
     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;
     }



4.
     public static void printBinaryNumber( int n )
     {
         if( n > 1 )
             printBinaryNumber( n / 2 );
         printBinaryDigit( n % 2 );
     }