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

1. (10 points) True or false?
1. _____ An enum is a class.
2. _____ An enum may be abstract.
3. _____ A tree that consists of a single node has depth zero.
4. _____ If for(Thing thing : things) {...} is legal, then things is an Iterator.
5. _____ Strings in Java are terminated by a zero byte.
6. _____ A hashCode() method should return a number between 0 and the size of your array minus one.
7. _____ log₂1024 = 10.
8. _____ If two algorithms have the same Big-O running time, they are equally fast.
9. _____ If you implement equals, it should be reflexive, symmetric, and transitive.
10. _____ It doesn't make sense for a class's only constructor to be private.
    
    
2. (6 points) Assume you are writing an Employee class, and

   You want to do the following:	What interfaces, if any, must your Employee class implement?	What methods must your Employee class implement? (Show the complete signature.)
   Use Employee objects as keys in a HashMap
   Keep a SortedSet of Employee objects
   Be able to sort Employee objects by either their name field or their EmployeeId field

   
   
3. (9 points) Suppose you have the following BNF rule:   <foo> ::= "u" [ "x" ] | "w" { "y" }
   In the lists below, circle the <foo>s and cross out the non-<foo>s
   

   	uu	uw	w
   	ux	uxy	wy
   	uxx	uxwy	wyyy

   
   
4. (4 points) Draw a state machine to recognize <foo> objects, as defined in the previous question. Indicate which states are your start and final states. Do not include an error state.
   
   
   
   
   
   
5. (3 points) Tell what the major error is in the following Recognizer method:

       public boolean term() {
           if (!term()) return false;
           while (multiplyOperator()) {
               if (!term()) error("No term after '+' or '-'");
           }
           return true;
       }

6. (6 points) What order do you visit the nodes when you traverse this binary tree:

   In preorder? In inorder? In postorder?

   
   
7. (3 points) What is the difference between a data type and an abstract data type?
   
   
   
   
   
8. (4 points) Assume that array has been filled with randomly generated integers in the range 1 to 10. What is the expected running time (Big-O notation) of the following method?

       int findFive(final int ARRAY_SIZE, int[] array) {
           for (int i = 0; i < ARRAY_SIZE; i++) {
   	        if (array[i] == 5) return i;
           }
   	    return -1;
       }

9. (4 points) What is the running time (Big-O notation) of the following method?

       int log2(int n) {
           int result = 0;
           int power = 1;
           while (power < n) {
               result++;
               power = 2 * power;
           }
           return result;
       }

10. (2 points) What is the difference between a mutative transformer and an applicative transformer?
    
    
    
    
11. (6 points) Suppose you wish to time a method. List three ways to improve the accuracy of your timing.
    
    
    
    
    
    
12. (4 points) Put the following in order, best to worst: O(n²), O(2ⁿ), O(n), O(1), O(log n), O(n log n).
    
    

    (best)

    (worst)

    
    
13. (6 points) Suppose set1 and set2 are both objects of type Set. For each of the following, write a single Java statement to:
    
    
    1. Make set1 the union of the two sets
       
       
       
    2. Make set1 the intersection of the two sets
       
       
       
    3. Make set1 the difference (set1 - set2) of the two sets
       
       
       
    4. Set boolean isSubset to true if and only if set1 is a subset of set2
       
       
       
14. (18 points) List three methods declared by each of the following interfaces, with complete signatures. Do not include any inherited methods, for example, equals, or the methods that SortedSet inherits from Set.
    

    Collection
    Set
    SortedSet
    List
    Map
    SortedMap

    
    
    
15. (6 points) For each of the following sort methods, tell what the invariant is. (An informal description in English is OK.)
    

    Bubble sort
    Insertion sort
    Selection sort

    
    
    
16. (3 points) What methods are required to implement each of the following interfaces?
    
    
    1. Iterable
       
       
    2. Comparable
       
       
    3. Comparator
       
       
17. (8 points) State Dr. Dave's four rules for doing recursion.
    
    
    
    
    
    
    
    
    
    
    
18. (4 points) From Joel on Software, by Joel Spolsky:
    

    Schlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck. The next day Schlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck. The next day Schlemiel lpaints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?" "I can't help it," says Schlemiel. "Every day I get farther and farther away from the paint can!"

    
    Assuming that Schlemiel works continuously (not day by day) until the entire N yards of the road is painted, what is the running time in Big-O notation of Schlemiel the Painter's Algorithm?