1.

(a) Clearly this is O(N^2).

(b) For a quadratic algorithm, twice the input means
    four times the runningtime. 4*16 = 64 milliseconds.

(c) Add the items into a TreeSet. If any add returns
    false there is a duplicate. Running time is O(N log N)
    (N adds at O(log N) per add).
    Using a HashSet gets an O(N) algorithm (N adds at O(1) per add).


2.

(a)

public static Map computeSummary( String [ ] games )
{
    Map result = new TreeMap( );

    for( int i = 0; i < games.length; i++ )
    {
        Game g = GameFactory.makeGame( games[ i ] );
        addToMap( g.getWinner( ), g, result );
        addToMap( g.getLoser( ), g, result );
    }

    return result;
}

private static void addToMap( String team, Game g, Map result )
{
    List games = (List) result.get( team );
    if( games == null )
    {
        games = new ArrayList( );
        result.put( team, games );
    }

    games.add( g );
}

(b)

public static List mostGames( Map gameSummary )
{
    int maxGames = 0;
    List result = new ArrayList( );
    Set  entries = gameSummary.entrySet( );
    Iterator itr = entries.iterator( );

    while( itr.hasNext( ) )
    {
        Map.Entry thisEntry = (Map.Entry) itr.next( );
        int thisGames = ((List)thisEntry.getValue( )).size( );

        if( thisGames < maxGames )
            continue;
        else if( thisGames > maxGames )
        {
            maxGames = thisGames;
            result = new ArrayList( );      // old result superceded
        }

        result.add( thisEntry.getKey( ) );  // the team name
    }

    return result;        
}


3.

public static int getWaterArea( GridElement pos )
{
    Collection waterElements = new HashSet( );
    getWaterArea( pos, waterElements );
    return waterElements.size( );
}

private static void getWaterArea( GridElement pos, Set alreadyUsed )
{
    if( !alreadyUsed.contains( pos ) && pos.containsWater( ) )
    {
        alreadyUsed.add( pos );

        GridElement [] adj = pos.getAdjacent( );
        for( int i = 0; i < adj.length; i++ )
            getWaterArea( adj[ i ], alreadyUsed );
    }
}