Please keep all answers short and to the point.

1. (4 points) Write the BNF to define a <pair>, where a "pair" consists of two items, separated by a comma, and surrounded by parentheses; an "item" can be either a number or another pair. For example, (5, (13, 3)). Assume that <number> has already been defined.
   
   
   
   
   
2. (4 points) Write a boolean pair() method to recognize a "pair" as defined in the previous question. You can assume the existence of other methods to recognize the various pieces of a "pair."
   
   
   
   
   
   
   
   
3. (6 points) Write a Java 5 enum named WEEKDAY, enumerating the seven days of the week, with boolean method isWorkDay(). isWorkDay() should return true for all days except Saturday and Sunday. Use proper capitalization (days of the week should be all caps).
   
   
   
   
   
   
   
   
   
   
4. (3 points) Why is the following illegal?    if (myList instanceof ArrayList<Integer>) {...}
   
   
   
   
   
5. (6 points) You have a class Person, where each Person has a String name instance variable. You want to create a set of Persons, sorted by name (and never sorted any other way).
   
   
   1. Using one of Java's generic collections, write a statement to declare and define a set of Person.
      
      
      
      
   2. Write the method or methods you need to add to the Person class to keep the set of Persons in sorted order.
      
      
      
      
      
      
6. (3 points) For classes that implement hashCode() (such as String), what range of values is returned by the hashCode() method?
   
   
   
7. (12 points) For this binary tree, tell in what order the nodes would be visited by each of the following techniques:
   
   
   1. Preorder
      
      
   2. Inorder
      
      
   3. Postorder
      
      
   4. Depth-first search
      
      
   5. Breadth-first search
      
      
   6. Depth-first iterative-deepening search
      
      
      
8. (5 points) A two-byte (16 bit) integer has five 1 bits in the first byte, and three 1 bits in the second byte. How many such integers are there?
   
   
   
9. (10 points) Given the following characters and their relative frequencies:
   

   Tell how many bits would be required for each character in a fixed-width encoding. Construct a Huffman tree for the characters in the space provided. Show the Huffman encoding for each character in the space provided. Compute how many bits per character would be required, on average, for a long message in which the different characters appeared with the expected relative frequency. Show your work.

   Construct your tree in the area on the right:   Frequency: 25% 5% 15% 20% 35% Character: A B C D E Encoding:

10. (16 points) Assume you have created a Huffman tree and encoding table as in the previous question, but for K characters. You have a message that is N characters long. In each of the following parts, describe briefly (1) how to do the required task, and (2) how long it will take to do it (use Big-O notation).
    
    
    1. Using just the tree, but not the table, encode an N-character message.
       
       
       
       
       
       
    2. Using just the tree, but not the table, decode an N-character message.
       
       
       
       
       
       
    3. Using just the table, but not the tree, encode an N-character message.
       
       
       
       
       
       
    4. Using just the table, but not the tree, decode an N-character message.
       
       
       
       
       
       
       
11. (12 points) A row of coins (pennies, nickels, dimes, quarters) is laid out in a line, in random order. One end of the line is the "front". Two players alternate turns; at each turn, a player may either (1) take the coin at the front of the line, or (2) give the coin at the front of the line to the opponent, and take the next coin. (For example, given 5 10 ..., a player may either take the 5, or give the 5 to the opponent and take the 10.) The object is to collect the most money.
    
    
    1. Briefly describe a greedy algorithm for playing this game.
       
       
       
       
    2. Show, with a short example, that the greedy algorithm is not optimal for this problem.
       
       
       
       
    3. Suggest a better algorithm for playing this game, and briefly indicate how the algorithm might be applied. (Just give me the basic idea, don't go into a lot of detail.)
       
       
       
       
       
       
       
12. (8 points) Here is a method for counting the nodes in a binary tree:
    

    int count = 0;

void countNodes(BinaryTree b) {
    if (b == null) return;
    count++;
    countNodes(b.getLeftChild());
    countNodes(b.getRightChild());
}


    1. Which of Dr. Dave's four rules of doing recursion does this violate?
       
       
       
    2. What are the possible consequences of violating this rule?
       
       
       
       
13. (4 points) You have a constructor Fraction(int numerator, int denominator) which should throw an IllegalArgumentException if denominator == 0. Write a JUnit method to test that it throws the exception correctly.
    
    
    
    
    
    
    
14. (6 points) Design a Couples ADT to represent a set of married couples. The only accessor method will be Person getSpouse(Person p) which, given one person in a couple, returns the other person. Your operations should make it possible to create any Couples, and to transform any Couples into any other Couples. Provide a necessary and sufficient set of constructors and methods (no convenience methods) to achieve this. Do not tell what each method does; just choose self-explanatory names for your methods.
    
    
    
    
    
    
    
    
    
    
    
    
15. (4 points) Describe the data structure or structures you would use to implement the getSpouse method (from the previous question) in linear time.