CIT 594 Final Exam Spring 2005, Dave Matuszek |
KEY |

Please keep all answers short and to the point.

- (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,

. Assume that(5, (13, 3)) `<number>`

has already been defined.

`<pair> ::= "(" <item> "," <item> ")"`

<item> ::= <number> | <pair>

- (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;

} - (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;

}

}

- (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.`

- (6 points) You have a class
`Person`

, where each`Person`

has a`String name`

instance variable. You want to create a set of`Person`

s, sorted by`name`

(and never sorted any other way).

- Using one of Java's generic collections, write a statement to declare
and define a set of
`Person`

.

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

- Write the method or methods you need to add to the
`Person`

class to keep the set of`Person`

s 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.

- Using one of Java's generic collections, write a statement to declare
and define a set of
- (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.`

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

- Preorder

`A B D F G C E`

- Inorder

`B F D G A E C`

- Postorder

`F G D B E C A`

- Depth-first search

`A B D F G C E`

- Breadth-first search

`A B C D E F G`

- Depth-first iterative-deepening search

`A A B C A B D C E A B D F G C E`

- Preorder
- (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`

- (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.

`3`

- 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``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.

- Tell how many bits would be required for each character in a fixed-width
encoding.
- (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).

- Using just the
but not the table,*tree,*an**encode**`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)

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

`For each bit sequence, step down the tree: O(log K)`

Do this N times: O(N log K)

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

`Looking up one character should be constant time: O(1)`

Do this for each of N characters: O(N)

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

`For each character, search K/2 locations on average: O(K)`

Do this for each of N characters: O(K*N)

- Using just the
- (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.

*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)

- 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)`

- 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.`

- (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());

}

- Which of Dr. Dave's four rules of doing recursion does this violate?

`Don't alter nonlocal variables.`

- 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.`

- Which of Dr. Dave's four rules of doing recursion does this violate?
- (4 points) You have a constructor
`Fraction(int numerator, int denominator)`

which should throw an`IllegalArgumentException`

if

. Write a JUnit method to test that it throws the exception correctly.denominator == 0

`public void testConstructor( ) {`

try {

new Fraction(1, 0);

fail();

}

catch (Exception e) { }

}

- (6 points) Design
`Couples`

ADT to represent a set of married couples. The*only*accessor method will be

which, given one person in a couple, returns the other person. Your operations should make it possible to create anyPerson getSpouse(Person p) `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

- (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.`