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) For a quadratic algorithm, when N is increased
       by a factor of 4, the running time increases
       by a factor of 4^2 = 16. So the time will be 64 sec.
   (c) Each binary search is O( log N ), and
       there are at most N, so the total is O( N log N ).


2. (a) toString and contains are O( N ), addLast is 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 boolean contains( AnyType x )
       {
           for( Node<AnyType> p = first; p != null; p = p.next )
               if( p.data.equals( x ) ) 
                   return true;

           return false;
       }

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



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 printReverse( BufferedReader in ) throws IOException
     {
         String oneLine = in.readLine( );
     
         if( oneLine == null )
             in.close( );
         else
         {
             printReverse( in );
             System.out.println( oneLine );
         }
     }