<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.
boolean pair() method to recognize a "pair"
as defined in the previous question...Most everybody got this. Good job!
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.
if
(myList instanceof ArrayList<Integer>) {...} Again, most everyone got this right.
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)... Mostly well done.
hashCode() (such as String),
what range of values is returned by the hashCode() method?Mostly right.
,
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! * 3!) * 8!/(3! * 5!) = 56 * 56 = 3136
Most common error: Adding rather than multiplying.
|
|
||||||||||||||||||||||||
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 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.
- Using just the tree, but not the table, decode
an N-character message.
- Using just the table, but not the tree, encode
an N-character message.
- 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 beO(N*K log K) . I gave credit for either answer.
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.
Most people did well on this.
Fraction(int numerator, int denominator)
which should throw an IllegalArgumentException if denominator
== 0 Most people did well on this.
Couples ADT to represent a set of
married couples. The only accessor method will be Person 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?
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.)