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.

(a) The running time is O( N^3 ) because of the three nested loops.

(b) For an O( N^3 ) algorithm, double the input means 8 (2*2*2) times
    as long to run. So, it takes 32 milliseconds.

(c) Use a map in which the keys are the items, and the values
    are the number of occurrences. As an item is seen, update
    the map accordingly. Using a TreeMap, where each operation
    is O( log N ), you get an O( N log N ) algorithm.

    Alternate: use Arrays.sort, which uses mergesort, after which
    you can see if there is any i for which a[ i ] and a[ i + 2 ]
    match. Since mergesort is O( N log N ), and the subsequent scan
    is O( N ), you get an O( N log N ) algorithm.


2.

(a)
  public LinkedList( )
  {
    beginMarker = new Node( null, null, null );
    endMarker   = new Node( null, beginMarker, null );
    beginMarker.next = endMarker;
  }

(b)
    // presumptively cannot be called on beginMarker
  public void addBefore( Object x, Node p )
  {
    Node n = new Node( x, p.prev, p );
    p.prev = n;
    n.prev.next = n;
  }

(c)
  public void addFirst( Object x )
    { addBefore( beginMarker.next ); }

  public void addLast( Object x )
    { addBefore( endMarker ); }


3. 
  public static Map inverseMap( Map m )
  {
    Map result = new TreeMap( );

    Iterator itr = m.entrySet( ).iterator( );
    while( itr.hasNext( ) )
    {
      Map.Entry thisEntry = (Map.Entry) itr.next( );
      Object thisKey = thisEntry.getKey( );
      List thisList = (List) thisEntry.getValue( );

      Iterator itr2 = thisList.iterator( );
      while( itr2.hasNext( ) )
      {
        Object thisValue = itr2.next( );
        List inverseList = (List) result.get( thisValue );
        if( inverseList == null )
        {
          inverseList = new ArrayList( );
          result.put( thisValue, inverseList );
        }
        inverseList.add( thisKey );
      }
    }

    return result;
  }



4.
  Some notes: efficient implementation for both ArrayList and LinkedList
  implies that you cannot use get (so you need iterators).

  public List getEvenElements( List items )
  {
    List result = new LinkedList( ) );
    getEvenElements( result, items.iterator( ) );

    return result;
  }

  private void getEvenElements( List result, Iterator current )
  {
    if( current.hasNext( ) )
    {
       result.add( current.next( ) );
       if( current.hasNext( ) )
         current.next( );

       getEvenElements( result, current );
    }
  }        



VERSION B

1.

(b) For an O( N^3 ) algorithm, triple the input means 27 (3*3*3) times
    as long to run. So, it takes 81 milliseconds.


2. Note there is a presumption that beginMarker and end
   point at the same node (the beginMarker) if the list is empty.
   There are other interpretations, and I accepted those if
   they were done consistently.


(a)
  public void makeEmpty( )
  {
    beginMarker = end;
    end.next = end.previous = null;
  }

    OR

  public void makeEmpty( )
  {
    beginMarker = end = new Node( null, null, null );
  }

    OR

  public void makeEmpty( )
  {
    while( !isEmpty( ) )
      removeFirst( );
  }


(b)
  public void addAfter( Object x, Node p )
  {
    Node n = new Node( x, p, p.next );
    p.next = n;

    if( p == end )
      end = n;
    else
      n.next.prev = n;
  }

(c)
  public void addFirst( Object x )
    { addAfter( beginMarker ); }

  public void addLast( Object x )
    { addAfter( end ); }



4.
  See comments for Version A. Version B described getOddElements
  but then asked for getEvenElements. Either would get you credit.
  Below is getOddElements.

  public List getOddElements( List items )
  {
    List result = new LinkedList( ) );
    Iterator itr = items.iterator( );

    if( itr.hasNext( ) )
      itr.next( );

    getOddElements( result, itr );

    return result;
  }

  private void getOddElements( List result, Iterator current )
  {
    if( current.hasNext( ) )
    {
       result.add( current.next( ) );
       if( current.hasNext( ) )
         current.next( );

       getEvenElements( result, current );
    }
  }        


VERSION C

1.

(b) For an O( N^3 ) algorithm, double the input means 8 (2*2*2) times
    as long to run. Conversily, one half the input means 1/8 times
    as long to run, so the answer is 1000 milliseconds.


2.

(a)
  public void makeEmpty( )
  {
    begin = endMarker;
    endMarker.next = endMarker.previous = null;
  }

    OR

  public void makeEmpty( )
  {
    begin = endMarker = new Node( null, null, null );
  }

    OR

  public void makeEmpty( )
  {
    while( !isEmpty( ) )
      removeFirst( );
  }

(b)
  public void addBefore( Object x, Node p )
  {
    Node n = new Node( x, p.prev, p );
    p.prev = n;

    if( p == begin )
      begin = n;
    else
      n.prev.next = n;
  }

(c)
  public void addFirst( Object x )
    { addBefore( begin ); }

  public void addLast( Object x )
    { addBefore( endMarker );  }






4.
  Note: efficient implementation for both ArrayList and LinkedList
  implies that you cannot use get (so you need iterators).

  public List getDoubleElements( List items )
  {
    List result = new LinkedList( ) );
    getDoubleElements( result, items.iterator( ) );

    return result;
  }

  private void getDoubleElements( List result, Iterator current )
  {
    if( current.hasNext( ) )
    {
       Object val = current.next( );

       result.add( val );
       result.add( val );

       getDoubleElements( result, current );
    }
  }        



VERSION D

1.

(b) For an O( N^3 ) algorithm, ten times the input means 1000 (10*10*10) times
    as long to run. Conversily, one tenth the input means 1/1000 times
    as long to run, so the answer is 8 milliseconds.


2.

(a)
  public LinkedList( )
  {
    begin = endMarker = new Node( null, null, null );
  }

(b)
    // presumptively cannot be invoked on endMarker
  public void addAfter( Object x, Node p )
  {
    Node n = new Node( x, p, p.next );
    p.next = n;
    n.next.prev = n;
  }

(c)
  public void addFirst( Object x )
    { begin = new Node( x, null, begin ); begin.next.prev = begin; }

  public void addLast( Object x )
    { if( begin == endMarker ) addFirst( x ); else addAfter( endMarker.prev ); 




4.
  Note: efficient implementation for both ArrayList and LinkedList
  implies that you cannot use get (so you need iterators).

  public List getReverse( List items )
  {
    List result = new LinkedList( ) );
    getReverseElements( result, items.iterator( ) );

    return result;
  }

  private void getReverseElements( List result, Iterator current )
  {
    if( current.hasNext( ) )
    {
       Object val = current.next( );
       getReverseElements( result, current );
       result.add( val );
    }
  }