# Average

N (number of students taking exam), 30.
Mean (average), 67.00.
Standard deviation, 17.31.

 ` FINAL EXAM * * * * * * * * * * * * * * * *** * ** * *** ** * **....:....|....:....|....:....|....:....|....:....|....:....|....:....|....:....|....:....|....:....| 10 20 30 40 50 60 | 70 80 90 100 mean ` `WEIGHTED TOTALS *20% Midterm, 30% Final, 50% Programs * * * ** * * * * * * * * * ** ** ***** * **** *....:....|....:....|....:....|....:....|....:....|....:....|....:....|....:....|....:....|....:....| 10 20 30 40 50 60 70 80 | 90 100 mean `

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.

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

2. (4 points) Write a `boolean pair()` method to recognize a "pair" as defined in the previous question...

Most everybody got this. Good job!

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

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.

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

Again, most everyone got this right.

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

6. (3 points) For classes that implement `hashCode()` (such as `String`), what range of values is returned by the `hashCode()` method?
Mostly right.

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

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
Most common error: Adding rather than multiplying.

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, since 22 = 4 < 5 characters < 23 = 8.

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

Remember to add the two smallest numbers at each step!

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.

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

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.

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.

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 be O(N*K log K). I gave credit for either answer.

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.

Everyone got this right.

2. 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.  :)

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

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

Most people did well on this.

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.

Most people did well on this.

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.

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?

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