CIT 594 Final Exam
Spring 2005, Dave Matuszek
KEY

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.

         <pair> ::= "(" <item> "," <item> ")"
         <item> ::= <number> | <pair>


  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."
        boolean pair() {
            if (!symbol("(")) return false;
            if (!number() && !pair()) error();
            if (!symbol(",")) error();
            if (!number() && !pair()) error();
            if (!symbol(")") error();
            return true;
        }
  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).
        public enum WEEKDAY {
            SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY;

            boolean isWorkDay() {
                return this != SUNDAY && this != SATURDAY;
            }
        }
  4. (3 points) Why is the following illegal?    if (myList instanceof ArrayList<Integer>) {...}

         Because of erasure, the generic information <Integer> is not known at run time.

  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.

      Set<Person> people = new TreeSet<Person>;

    2. Write the method or methods you need to add to the Person class to keep the set of Persons in sorted order.
          public int compareTo(Object o) {
              Person p = (Person)o;
              return name.compareTo(p.name);
          }
      If the same person can be represented by more than one Person object, you also need to redefine equals.


  6. (3 points) For classes that implement hashCode() (such as String), what range of values is returned by the hashCode() method?
         All 32-bit integers; that is, Integer.MIN_VALUE to Integer.MAX_VALUE.

  7. (12 points) For this binary tree, tell in what order the nodes would be visited by each of the following techniques:

    1. Preorder
           A B D F G C E
    2. Inorder
           B F D G A E C
    3. Postorder
           F G D B E C A
    4. Depth-first search
           A B D F G C E
    5. Breadth-first search
           A B C D E F G
    6. Depth-first iterative-deepening search
           A A B C A B D C E A B D F G C E

  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?
         8!/(5! * 3!) * 8!/(3! * 5!) = 56 * 56 = 3136

  9. (10 points) Given the following characters and their relative frequencies:
    1. Tell how many bits would be required for each character in a fixed-width encoding.
           3

    2. Construct a Huffman tree for the characters in the space provided.

    3. Show the Huffman encoding for each character in the space provided.

    4. 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
    000
    001
    01
    11
         0.25*2 + 0.05*3 + 0.15*3 + 0.20*2 + 0.35*2
         =  0.80*2 + 0.20 * 3
         = 1.6 + 0.6  
          =  2.2 bits/char, on average


          Your encodings may differ, but each should be the same number of bits as shown.

  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.

           Search the tree for each character: 1/2 * K * average depth =1/2 * K * log K = O(K log K)
           Do this for each of N characters: O(N*K log K)



    2. Using just the tree, but not the table, decode an N-character message.

           For each bit sequence, step down the tree: O(log K)
           Do this N times: O(N log K)



    3. Using just the table, but not the tree, encode an N-character message.

           Looking up one character should be constant time: O(1)
           Do this for each of N characters: O(N)



    4. Using just the table, but not the tree, decode an N-character message.

           For each character, search K/2 locations on average: O(K)
           Do this for each of N characters: O(K*N)




  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.

           Take the first or the second coin, whichever is larger;
           OR, take the larger of (first coin, second coin - first coin)


    2. Show, with a short example, that the greedy algorithm is not optimal for this problem.

           1, 5, 1, 25, ...   (taking the 5 means your opponent can get the 25)

    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.)
      An alpha-beta search works very well here; at each node choose either option 1 or option 2, evaluate the results after searching ahead for a large number of moves, and choose the best PBV.

  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?
           Don't alter nonlocal variables.

    2. What are the possible consequences of violating this rule?

           If you don't remember to reset "count" after each call, the method gives the wrong answers.

  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.

         public void testConstructor( ) {
              try {
                   new Fraction(1, 0);
                   fail();
              }
              catch (Exception e) { }
         }
  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.

         public Couples( ) // constructor

         public void addCouple(Person p, Person q)

         public void remove(Person p)
              ...or you could write this with two Person arguments, but it's unnecessary and unhelpful


  15. (4 points) Describe the data structure or structures you would use to implement the getSpouse method (from the previous question) in linear time.
    A single Map, such as a HashMap, is all that's needed. Put each couple in the map twice, once with each Person as the key and the other Person as the value.