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 ), because of nested loops, and because
       calls to get are constant time.
   (b) O( N^3 ), because each call to get is O( N ) and there
       are O( N^2 ) 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.



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

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

   (c)
       public void removeFirst( )
       {
           if( beginMarker.next == endMarker )
               throw new IllegalStateException( );
           else
           {
               beginMarker.next = beginMarker.next.next;
               beginMarker.next.prev = beginMarker;
           }
       }

   (d)
       public void addLast( AnyType x )
       {
            endMarker.prev = endMarker.prev.next
                           = new Node<AnyType>( x, endMarker.prev, endMarker );
       }



3.
     public static Map<String,List<String>> groups( String [ ] arr )
     {
         Map<String,List<String>> result = new TreeMap<String,List<String>>( );

         for( String str : arr )
         {
             String digits = wordToNumber( str );
             List<String> words = result.get( digits )

             if( words == null )
             {
                 words = new ArrayList<String>( );
                 result.put( digits, words );
             }
             words.add( str );
         }

         return result;
     }



4.
     public static Set<String> expandEntry( Entry e )
     {
         Set<String> result = new HashSet<String>( );
         expandEntry( e, result );
         return result;
     }

     private static void expandEntry( Entry e, Set<String> result )
     {
         if( e.isString( ) )
             result.add( e.getString( ) );
         else
             for( Entry ent : e.getList( ) )
                 expandEntry( ent, result );
     }