Final Exam Grades
and CommentsCIT 594, Spring
2005 |

N (number of students taking exam), 30.

Mean (average), 67.00.

Standard deviation, 17.31.

FINAL EXAM * |

WEIGHTED TOTALS * |

**In general: ***Read the question!* Many of you would have gotten
more points if you took a little more time to understand what I was asking before
you answered.

- (4 points) Write the BNF to define a
`<pair>`

...

`The complete syntax for BNF contains four symbols:`**::= < >**and**|**. Extended BNF adds four more:**{ } [ ]**, and wasn't even needed for this question. Neither uses parentheses. Surprisingly few people took the 10 minutes necessary to learn the syntax.

- (4 points) Write a
`boolean pair()`

method to recognize a "pair" as defined in the previous question...

`Most everybody got this. Good job!`

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

`The study guide said, "Some of the following questions will be on the final exam." This was one of them.`

You should remember that an enum is a new kind of class. Most people who got this wrong ended the class (with a closing brace) right after the list of names of days, leaving noplace to put the method.

- (3 points) Why is the following illegal?
`if (myList instanceof ArrayList<Integer>) {...}`

`Again, most everyone got this right.`

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

`Mostly well done.`

- (3 points) For classes that implement
`hashCode()`

(such as`String`

), what range of values is returned by the`hashCode()`

method?

`Mostly right.`

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

`Mostly right. A few errors were clearly just insufficient care. The hardest one was Depth First Iterative Deepening, where nodes could be visited more than once (a couple people did a good job with the "iterative deepening" part, but did a breadth-first iterative deepening.)`

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

`Most common error: Adding rather than multiplying.`

- (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, since 2`^{2}= 4 < 5 characters < 2^{3}= 8.

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

`Remember to add the two`*smallest*numbers at each step!

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

`You got the points for this if you computed the average correctly for the binary tree you built, even if the binary tree was wrong.`

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

`I asked`*how*to do the required task. "Use the tree to encode the characters" is**not**a sufficient answer! Also, "just the tree" means you use just the tree, not some data structure built from the tree. Similarly comments apply to the other parts of this question.

In both this part and part (d), you need to recognize that a search is required.

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

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

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

Actually, I later realized that you had to do the search for each of log K bit patterns, so the correct answer should beO(N*K log K) . I gave credit for either answer.

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

`Everyone got this right.`

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

`I'm pretty disappointed with this one. I got many answers of the form:`"

"I used these numbers: I played greedy and I lost.

`Guess what? "Losing" doesn't mean you didn't play optimally. "Optimal" means you used the best strategy; "not optimal" means there is a better strategy. To get points for this, you had to show an example where the greedy strategy gives you less money than some other strategy. For example, "1 5 1 25": if you take the 5 you get 6, but if you take the 1 you get 27.`

Also, though this did not enter into my grading: I said "collect the most money," I didn't say "collect more money than your opponent." I'm surprised at how many people assumed there had to be a winner and a loser.

And just FYI, we don't have 2, 7, or 20 cent coins. :)

- 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, but other, simpler algorithms were also given credit. A* looks for a goal node, which is hard to define for this question, hence a poor choice.`

- (8 points) Here is a method for counting the nodes in a binary tree: ...

`Most people did well on this.`

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

`Most people did well on this.`

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

`This is my poster child for "read the question."`

"Design a**Couples**" -- I say "Couples"*three times*in the question; I*never*say "Couple." There may or may not be a Couple class.

"**ADT**" -- An "ADT" is an**Abstract**Data Type; it tells what operations you have,**not**how you implement them.

"to represent a**set**of married couples." -- Not just a single couple.

"...constructors and methods..."

**constructor: A**lot of people wanted "Couples(Person p, Person q)", which I guess makes sense if you think by "a set of married couples" I meant a single couple. Otherwise, think about the constructors in the Collections interfaces--how many of them assume you collection must not be empty?

**methods:**The basic operations on any set are adding a value and removing a value (and finding a value, which I gave you). So marry(Person, Person) and divorce(Person) are the methods that should be obvious.

"to transform any**Couples**" -- I don't think a method to change one's spouse (rather than simple divorce and marriage) is particularly useful. Also, without either promoting or rejecting gay marriage, but purely on technical grounds, making your code dependent on gender (e.g. man as the first argument, woman as the second) isn't a good idea.

"**no convenience methods**" -- You should have no unnecessary methods. A necessary method is one that, if removed, would prevent you from being able to "create any Couples, and to transform any Couples into any other Couples."

"choose**self-explanatory names**" -- Can anyone tell me what the**transform**method is supposed to do?

- (4 points) Describe the data structure or structures you would use to implement
the
`getSpouse`

method (from the previous question) in linear time.

`There was an error in the question: I meant to say`**constant**time. My answer was "A single Map, such as a HashMap, is all that's needed." You can get linear time from almost any data structure, so there were a lot of correct answers to this one. (I also accepted constant time answers.)