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.
   
   Lists are ordered; Sets are not.
   Lists may have duplicate elements; Sets cannot.
   
   
2. [2 points] Tell two differences between Java's Map and TreeMap.
   
   Map is an interface; TreeMap is a class.
   TreeMaps are sorted; Maps are not (necessarily) sorted.
   
   
3. [2 points] What is the most important difference between a "pointer" and a "reference"?
   
   You can do arithmetic on pointers.
   
   
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?
   
   Profile the program to determine where the bottleneck is.
   
   
5. [8 points] True or false:
   
   
   1. FALSE If you need random numbers for several different purposes in your program, you should create a different random number generator for each.
      
      
   2. TRUE In a JUnit class, every public void testXxx() method will be called automatically.
      
      
   3. TRUE Every object has an equals method.
      
      
   4. TRUE Every object has a hashCode method.
      
      
   5. TRUE A beta cutoff occurs when you decide that your opponent will not explore beneath a node.
      
      
   6. TRUE Genetic algorithms are a kind of state-space searching.
      
      
   7. FALSE Quicksort is widely used because it is always O(n log n) time.
      
      
   8. TRUE Breadth-first searching requires more memory than depth-first searching.
      
      
      
6. [5 points] Briefly define each of the following:
   
   
   1. Unit test -- A test of a single class.
      
      
      
   2. Reflection -- The ability of a program to examine its own structure.
      
      
      
   3. Dynamic programming -- Building a solution from the bottom up, storing and using the solutions to simpler cases.
      
      
   4. Abstract data type -- Specification of data values and operations on those values, but saying nothing about the implementation.
      
      
   5. Refactoring -- Modifying a program to improve its structure without changing its functionality.
      
      
      
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?
      (1) A reference to either the BooleanArray or the bits variable
      (2) An index into the array
      
      
   2. [6 points] Write the complete header line of each of the three required methods:
      
      
      1. public boolean hasNext()
         
         
      2. public Object next()
         
         
      3. public void remove()
         
         
   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?
      
      Throw an UnsupportedOperationException.
      
      
8. [4 points] State your instructor's four rules for doing recursion.
   
   
   1. Do the base case(s) first.
      
      
   2. Recur only with a simpler case.
      
      
   3. Don't modify nonlocal variables.
      
      
   4. Don't look down!
      
      
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).
   
   This turned out to be a bad question. It was supposed to test whether you could do recursion, but ended up testing how careful you were to avoid null pointer exceptions. Here's my best answer:
   
   public boolean equals(BinaryTree that) {
      if (that == null) return false; // note: this==null is impossible
      return safeEquals(this.value, that.value) &&
             safeEquals(this.leftChild, that.leftChild) &&
             safeEquals(this.rightChild, that.rightChild);
   }
   public boolean safeEquals(Object obj1, Object obj2) {
      if (obj1 == obj2) return true;
      if (obj1 == null || obj2 == null) return false;
      return obj1.equals(obj2);
   }
   
   
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.
    
    <integer> ::= ["+" | "-"] <digit> { <digit> }
    
    
    
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, O <= f(n) <= cg(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, O <= cg(n) <= f(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, O <= c₁g(n) <= f(n) <= c₂g(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?
       Best: A String such as: String key = row + "," + column; //best because hashCode is already defined for Strings
       OK: An object containing row and column (must define equals, hashCode)
       Wrong: An arithmetic combination of row and column (cannot guarantee uniqueness)
       Very wrong: anything that depends on the value of the double
       
    2. [3 points] What would you use for values?
       
       The double wrapped in a Double.
       
       
    3. [2 points] Briefly mention one disadvantage of this implementation.
       No easy way to step through values in a row or column
       
       I did not want you to write code for this question, but in case you're curious, here is what it would look like:

       import java.util.HashMap; public class SparseArray { HashMap map = new HashMap(500); public void store(int row, int column, double value) { map.put(row + "," + column, new Double(value)); } public double fetch(int row, int column) { Object obj = map.get(row + "," + column); if (obj == null) return 0.0; else return ((Double) obj).doubleValue(); } }

       
       
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.
       Usual answer: Check if the total of all numbers is divisible by 3.
       Most interesting answer: Subtract the two largest values from the total, check whether the result is at least as large as second largest value.
       Most amusing (correct) answer: Check if set contains at least three values.
       
       
    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).
       
       Use brute force: Try all possible ways of putting the values into three piles, until you find a solution or determine that no solution exists.
       
       Note: It is wrong to assume that if there is a solution, and you find one pile of the correct size, then the remaining numbers can be put into two equal piles. Consider {1, 2, 2, 3, 3, 4, 6}, adding to 21; This does have a solution, but if you put all the odd numbers into one pile, {1, 3, 3}, the remaining numbers cannot be solved.
       
       
    3. [2 points] What is the running time of your algorithm? Why?
       
       Despite the popularity of O(n!), the correct answer is O(3ⁿ). The first number can be put into any of 3 piles, the second into any of three piles, ..., up to the n-th number. 3*3*3*...*3 = 3ⁿ.
       
       
    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).
       
       Sort the numbers largest to smallest. Starting with the largest value, put each value into the pile with the most remaining room. (This is a greedy algorithm.)
       
       
    5. [2 points] What is the running time of your approximate algorithm? Why?
       
       O(n log n) to sort, then an O(n) pass to put in piles--therefore, O(n log n).
       
       
16. [2 points] What two assumptions are made by the alpha-beta algorithm?
    
    
    1. Your opponent's heuristics are similar to yours.
       
       
    2. The further ahead you can look, the more trustworthy are your heuristic values. (See my alpha-beta PowerPoint presentation, slide 9.)
       
       
17. [6 points] For the following binary tree:
    
    1. In what order would the nodes be visited by a preorder walk?
       A B D C E
       
    2. In what order would the nodes be visited by an inorder walk?
       D B A C E
       
    3. In what order would the nodes be visited by a postorder walk?
       D B E C A
       
    4. In what order would the nodes be searched by a breadth-first search?
       A B C D E or A C B E D
       
       
    5. In what order would the nodes be searched by a depth-first search?
       A B D C E or A C E B D
       
       
    6. In what order would the nodes be searched by a depth-first iterative deepening search?
       A A B C A B D C E or A A C B A C E B D
       
       
    (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?
       To choose the next node to explore
       
       
    2. What is N?
       The node being evaluated
       
       
    3. What is g(N)?
       The known distance or cost from the root to N
       
       
    4. What is h(N)?
       The estimated distance or cost from N to a goal node
       
       
    5. What is f(N)?
       The estimated distance or cost from the rootto a goal node along a path that passes through N
       (Sorry, g(N) + h(N) is not an acceptable answer.)
       
       
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?
    
    To get consistent behavior (usually while testing)
    
    
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.
       
       For each code in the table, test if it is an initial substring of the message. If so, translate it and remove it from the input message.
       
       Harder to code: Make a hash table with codes as keys and letters as values. Try one bit, then two, then three, ..., until you find a code that doesn't return null. Translate and remove from the message.
    2. 
       
    3. [2 points] What is the running time of your algorithm? Why?
       
       If there are N codes and the message length is M, then we translate and remove N*M times. But removal entails copying the length M string, so O(N*M²).
       
       Harder approach: O(N) time to build the hash table, one constant-time search for every one of M bits plus O(M) to remove from table, so O(N*M²).
       
       
    4. [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.
       
       First, turn the encoding table into a binary tree (the reverse of the way it was created), so lookup is at worst O(log n). Then step along the length M string and do the translation, but don't modify the message string.
       
       
    5. [2 points] What is the running time of your faster algorithm? Why?
       
       O(N log N) time to build the binary tree. After that, each bit of the message (of M bits) requires constant time--either step down the tree, or translate and start over. Hence, O(N log N) + O(M) time--but N is small, so effectively O(M).
       
       
22. [2 points] When the statement Person p = new Person(); is executed,
    
    
    1. What is placed on the heap?
       Storage for the actual Person object.
       
       
    2. What is placed on the stack?
       Storage for the reference p.