Please keep all your answers short and to the point. Do not provide extra information that was not asked for.

1. (5 points) When is it appropriate for a class X to extend a class Y?
   
   When an X is a kind of Y.
   When it makes sense for X objects to have all the operations of class Y.
   
   
2. (5 points) An array implementation of a Stack class typically has one more method than it would if it were implemented as a linked list. What is that operation?
   
   A method to test if the stack is "full."
   
   
3. (5 points) Which of the following are methods of the Collection interface? (Cross out the ones that are not.)
   
   
   • boolean add(E o)
     
     
   • boolean addAll(Collection<? extends E> c)
     
     
   • void add(int index, E element)
     
     
   • Iterator<E> iterator()
     
     
   • Set<E> toSet(Collection<E>)


4. (5 points) Write the complete signature, including the return type and generics, for each of the following methods in the Collection interface:
   
   
   • add
     boolean add(E e)
     
     
   • contains
     boolean contains(Object o)
     
     
   • containsAll
     boolean containsAll(Collection<?> c)
     
     
   • iterator
     Iterator<E> iterator()
     
     
   • equals
     boolean equals(Object o)
     
     
5. (5 points) Draw a line between each set-theoretic operation and the Set method that implements it.
   

   addAll	(-> union)	union
   contains	(-> member)	intersection
   containsAll	(-> subset)	difference
   removeAll	(-> difference)	member
   retainAll	(-> intersection)	subset



6. (5 points) Suppose you have a singly-linked list declared as
      class MyList { int value; MyList next; ...}
   with a constructor
      MyList(int value, MyList next). Write a recursive method int last() to put in this class; the method should return the last value in the list. You may assume the list is not empty.
   
   private int last() {
       if (next == null) return value;
       else return next.last();
   }
   
   
7. (5 points) Write the iterative version of the int last() method described in the previous question.
   
   private int last() {
       MyList here = next;
       while (here.next != null) {
           here = here.next;
       }
       return here.value;
   }
   
   
   
8. (5 points) In an ADT, why is it a bad idea to have too many "convenience" methods?
   
   It makes it more difficult to understand the class as a whole.
   It makes it harder to recognize the "essential" operations.
   
   
9. (5 points) Suppose you frequently need to do a binary search on a list. Should you use a LinkedList or an ArrayList, and why?
   Use an ArrayList. Finding the n^th element of an array is O(1) time, but for a linked list it is O(n) time.
   
   
10. (3 points) In what order are the nodes of this binary tree traversed

    in preorder? A B C D E F in inorder? D C E F B A in postorder? D F E C B A

11. (5 points) The following code counts the number of digits in a positive integer variable number:

        int n = number;
        int count = 0;
        while (n > 0) {
            n = n / 10;
            count++;
        }

    How long (in Big-O terms) does this method take? Why?
    
    O(log n) time, because the number of digits in a number is the log₁₀ of the number.
    
    
    
12. (5 points) What two methods are found in a ListIterator but not in an Iterator?
    
    hasPrevious() and previous() (or: boolean hasPrevious() and E previous()).
    
    
    What does this tell you about Sun's implementation of LinkedList?
    
    It's probably implemented as a doubly-linked list.
    
    
    
13. (5 points) Under what circumstances will an Iterator method throw a ConcurrentModificationException?
    
    When the collection is modified during the iteration. (The exception is noticed when the iterator's hasNext() or next() method is called.)
    
    
14. (6 points) Write all BNF rules necessary to define <small integer>, where a "small integer" is a number in the range -99 to 99.
    <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    <small integer> ::= <digit> | <digit> <digit> | - <digit> | - <digit><digit>
    (OR: <small integer> ::= [ - ] <digit> [ <digit> ] )
    
15. (5 points) Suppose <foo> ::= { [ a ] b } { c [ d ] }, where the brackets and braces are BNF metasymbols. Circle each of the following strings that are <foo>s, and cross out the ones that are not.
    
    
    1. a b c d
       
       
    2. a b c
       
       
    3. a a b d d
       
       
    4. a b b c d c c d
       
       
    5. d
       
       
16. (5 points) Draw a state machine to accept a string of 'A's and 'B's if it contains an even number of 'A's.
    
    
    
    
    
17. (4 points) If you want to put Vehicle objects into a HashSet, the Vehicle class must override both hashCode() and equals(Object). 
    
    
18. (4 points) If you want to put Vehicle objects into a TreeSet (which is a SortedSet), the Vehicle class must override both equals(Object) and compareTo(T) (OR compare(T, T)). 
    
    
19. (5 points) Describe the object created by the declaration new String[10][].
    
    An array of ten rows, each of which is capable of holding an array of Strings.
    
    
20. (8 points) What are Dave's four rules for doing recursion?
    Do the base cases first
    Recur only with a simpler case
    Don't modify and use nonlocal variables
    Don't look down