Please read each question carefully, and answer the question that is asked, not some related question. Keep answers brief--you have enough room for correct answers. Write legibly--if I can't read your answer, it's wrong.

1. [2 points] Tell two differences between Java's Set and List.
   
   
   
   
   
2. [2 points] Tell two differences between Java's Map and TreeMap.
   
   
   
   
   
   
3. [2 points] What is the most important difference between a "pointer" and a "reference"?
   
   
   
   
4. [2 points] Suppose your program is running too slowly, and you need to make it faster. What is the first thing you should do?
   
   
   
   
5. [8 points] True or false:
   
   
   1. _____ If you need random numbers for several different purposes in your program, you should create a different random number generator for each.
      
      
   2. _____ In a JUnit class, every public void testXxx() method will be called automatically.
      
      
   3. _____ Every object has an equals method.
      
      
   4. _____ Every object has a hashCode method.
      
      
   5. _____ A beta cutoff occurs when you decide that your opponent will not explore beneath a node.
      
      
   6. _____ Genetic algorithms are a kind of state-space searching.
      
      
   7. _____ Quicksort is widely used because it is always O(n log n) time.
      
      
   8. _____ Breadth-first searching requires more memory than depth-first searching.
      
      
      
6. [5 points] Briefly define each of the following:
   
   
   1. Unit test
      
      
      
   2. Reflection
      
      
      
   3. Dynamic programming
      
      
      
   4. Abstract data type
      
      
      
   5. Refactoring
      
      
      
      
7. [10 points total] Here is the definition of a class:
      public class BooleanArray {
       public boolean[] bits = new boolean[32];
   }
   If you were to write a BooleanArrayIterator class (implementing Iterator) for this class,
   
   
   1. [2 points] What instance variable or variables would you need?
      
      
      
      
   2. [6 points] Write the complete header line of each of the three required methods:
      
      
      1. 
         
         
      2. 
         
         
      3. 
         
         
   3. [2 points] Since a remove method for this class doesn't seem to make much sense, but Java requires that you have one, what should your remove method do?
      
      
      
      
8. [4 points] State your instructor's four rules for doing recursion.
   
   
   1. 
      
      
   2. 
      
      
   3. 
      
      
   4. 
      
      
9. [4 points] The following is a partial description of a BinaryTree class:

   public class BinaryTree {
      BinaryTree leftChild, rightChild;
      Object value;
      ...   }

   Write an instance method to determine whether two binary trees are equal (same shape, same values).
   
         public boolean equals(BinaryTree that) {







      }

   
10. [2 points] Use extended BNF to define <integer>. An integer should consist of an optional plus or minus sign, followed by one or more digits. Assume that <digit> has already been defined.
    
    
    
    
    
    
11. [2 points] A function f(n) is O(g(n)) if there exist positive constants c and N such that,
    for all n > N, _____________________ .
    
    
12. [2 points] A function f(n) is Ω(g(n)) if there exist positive constants c and N such that,
    for all n > N, _____________________ .
    
    
13. [2 points] A function f(n) is Θ(g(n)) if there exist positive constants c₁, c₂ and N such that,
    for all n > N, _____________________ .
    
    
14. [8 points total] It is possible to implement a two-dimensional sparse array of doubles using only a map (no linked lists), that provides both fetch and store operations. To do this,
    
    
    1. [3 points] What would you use for keys?
       
       
       
       
    2. [3 points] What would you use for values?
       
       
       
       
       
    3. [2 points] Briefly mention one disadvantage of this implementation.
       
       
       
15. [12 points total] Given a set of positive integers, for example, {19, 27, 42, ...}, suppose you want to sort these integers into three equal piles, so that the sum of the integers in each pile is the same.
    
    
    1. [1 point] Briefly describe a fast (linear time) test for whether the problem might have a solution.
       
       
       
       
    2. [4 points] Briefly describe an algorithm for finding an exact solution to this problem (just the general idea, don't tell me about details such as loops).
       
       
       
       
       
       
       
       
       
       
    3. [2 points] What is the running time of your algorithm? Why?
       
       
       
       
       
    4. [3 points] Briefly describe an algorithm for finding a reasonably good approximate solution to the problem (that is, the piles should be approximately equal).
       
       
       
       
       
       
       
       
       
       
       
       
    5. [2 points] What is the running time of your approximate algorithm? Why?
       
       
       
       
       
16. [2 points] What two assumptions are made by the alpha-beta algorithm?
    
    
    1. 
       
       
       
       
    2. 
       
       
       
17. [6 points] For the following binary tree:
    
    1. In what order would the nodes be visited by a preorder walk?
       
       
    2. In what order would the nodes be visited by an inorder walk?
       
       
    3. In what order would the nodes be visited by a postorder walk?
       
       
    4. In what order would the nodes be searched by a breadth-first search?
       
       
       
    5. In what order would the nodes be searched by a depth-first search?
       
       
       
    6. In what order would the nodes be searched by a depth-first iterative deepening search?
       
       
       
    (If there is more than one possible answer to any of the above, provide only one.)
    
    
18. [4 points] A message contains only the letters G, A, T, C in the proportions 1:2:4:8. That is, A is twice as likely to occur as G; T is twice as likely as A; and C is twice as likely as T. If you use a Huffman encoding, what is the average number of bits required per letter?
    
    
    
    
    
    
    
    
    
    
    
    
19. [5 points] The A* algorithm uses the formula  f(N) = g(N) + h(N).
    
    
    1. In A*, what are the computed f(N) values used for?
       
       
       
    2. What is N?
       
       
       
    3. What is g(N)?
       
       
       
    4. What is h(N)?
       
       
       
    5. What is f(N)?
       
       
20. [2 points] When you create a new random number generator, you can supply a seed. Briefly, why would you ever want to do this?
    
    
    
    
    
21. [12 points total] Suppose you are given a Huffman encoding (in the form of a table: A=01, B=1010, etc.) and a long message that has been encoded with it. You want to write a program as quickly and simply as possible to decode this message; you don't care how efficient the program is, so long as it isn't infeasibly slow (for example, exponential time is too slow).
    
    
    1. [4 points] Describe in English (do not write code) the algorithm you would use.
       
       
       
       
       
       
       
       
       
       
    2. [2 points] What is the running time of your algorithm? Why?
       
       
       
       
       
    3. [4 points] Now suppose your program is going to become part of a communications program, and needs to be made as fast as possible. Describe in English (do not write code) the algorithm you would use in this case.
       
       
       
       
       
       
       
       
    4. [2 points] What is the running time of your faster algorithm? Why?
       
       
       
       
       
22. [2 points] When the statement Person p = new Person(); is executed,
    
    
    1. What is placed on the heap?
       
       
       
    2. What is placed on the stack?