1.

(a) 
  public static int count( Collection c, String str )
  {
    int total = 0;

    Iterator itr1 = c.iterator( );
    while( itr1.hasNext( ) )
    {
      Iterator itr2 = ((Collection)(itr1.next())).iterator( );
      while( itr2.hasNext( ) )
        if( str.equals( itr2.next( ) ) )
          total++;
    }

    return total;
  }

(b) Running time is O( N^2 )

(c) For a quadratic algorithm, three times
    as much input means nine times as much time,
    so the result is 18 milliseconds.


2. 

(a)
  public void trim( )
  {
      // first, skip past all leading null data items
    while( first != null && first.data == null )
      first = first.next;

    if( first == null )
      return;

    Node p = first;

    while( p.next != null )
      if( p.next.data == null )
        p.next = p.next.next;
      else
        p = p.next;
  }


(b)
  public void trim( )
  {
    first = trim( first );
  }


  private Node trim( Node p )
  {
    if( p == null )
      return null;

    if( p.data == null )
      return trim( p.next );
    else
    {
      p.next = trim( p.next );
      return p;
    }
  }


3.

(a)
  public static Map computeCounts( String [ ] strings )
  {
    Map m = new HashMap( );

    for( int i = 0; i < strings.length; i++ )
    {
      Object val = m.get( strings[ i ] );
      if( val == null )
        m.put( strings[ i ], new Integer( 1 ) );
      else
        m.put( strings[ i ], new Integer( ((Integer) val).intValue( ) + 1 ) );
    }

    return m;
  }

  RUNNING TIME OF THIS ROUTINE IS O( N ).
  IF A TREEMAP IS USED, RUNNING TIME IS O( N log N )

(b)
  public static List mostCommonStrings( Map stringsAndCounts )
  {
    int maxCount = 0;

    Set s = stringsAndCounts.entrySet( );
    Iterator itr = s.iterator( );
    List result = null;

    while( itr.hasNext( ) )
    {
      Map.Entry thisPair = (Map.Entry) itr.next( );
      int thisCount = ( (Integer) thisPair.getValue( ) ).intValue( );

      if( thisCount > maxCount )
      {
         maxCount = thisCount;
         result = new ArrayList( );
         result.add( thisPair.getKey( ) );
      }
      else if( thisCount == maxCount )
         result.add( thisPair.getKey( ) );
    }

    return result;
  }

  RUNNING TIME OF THIS ROUTINE IS O( N ), where
  N is the number of different strings.
  THIS IS TRUE INDEPENDENT OF THE TYPE OF MAP.