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.

VERSION A

1. [SCORING BY PARTS: 10; 10; 15; 15]
  a. Removing from an ArrayList is an O(N) operation because elements
     have to be shifted to the left. There are N/2 removes, so the
     total cost is O(N^2).

  b. Removing from a LinkedList is an O(N) operation if only the index
     is specified because you have to hop down the list. As above, the
     total cost is O(N^2).

  c. For a quadratic algorithm, 3 times the input means 9 times the
     running time. So the estimate is 72 milliseconds.

  d. public static <AnyType> void removeEveryOtherItem( List<AnyType> list )
     {
         Iterator<AnyType> itr = list.iterator( );
         while( itr.hasNext( ) )
         {
             itr.next( );
             itr.remove( );
             if( itr.hasNext( ) ) 
                 itr.next( );
         }
     }


2. [SCORING BY PARTS: 20 for contains; 10 for Big-Oh; 20 for remove]
   [Missing p!null in contains -5; not using .equals =1]
   [Main two lines in remove is 12 pts; 2 for first; 2 for last; 4 for empty]
  a. public boolean contains( Object x )   // Runs in O(N)
     {
         for( Node p = first; p != null; p = p.next )
             if( p.data.equals( x ) ) 
                 return true;

         return false;
     }

  b. private void remove( Node p )
     {
         if( p == first && p == last )
             first = last = null;
         else if( p == first )
         {
             first = first.next;
             first.previous = null;
         }
         else if( p == last )
         {
             last = last.previous;
             last.next = null;
         }
         else
         {
             p.previous.next = p.next;
             p.next.previous = p.previous;
         }
     }

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 boolean hasSum( int [ ] arr, int sum )
     {
         return hasSum( arr, 0, arr.length - 1, sum );
     }

     private static boolean hasSum( int [ ] arr, int low, int high, int sum )
     {
         if( low > high )
             return sum == 0;
         else
             return hasSum( arr, low + 1, high, sum ) ||
                    hasSum( arr, low + 1, high, sum - arr[ low ] );
     }