CIT594 Midterm ExamSpring 2006 |
Name_________________________________________ |

Please keep all your answers short and to the point. Do not provide extra information that was not asked for.

- (10 points) True or false?
- _____ An
`enum`is a class. - _____ An
`enum`may be`abstract`. - _____ A tree that consists of a single node has depth zero.
- _____ If
`for(Thing thing : things) {...}`is legal, then`things`is an`Iterator`. - _____ Strings in Java are terminated by a zero byte.
- _____ A
`hashCode()`method should return a number between 0 and the size of your array minus one. - _____ log
_{2}1024 = 10. - _____ If two algorithms have the same Big-O running time, they are equally fast.
- _____ If you implement equals, it should be reflexive, symmetric, and transitive.
- _____ It doesn't make sense for a class's only constructor to be private.

- (6 points) Assume you are writing an
`Employee`class, andYou want to do the following: What interfaces, if any, must your Employee class implement? What methods must your Employee class implement? (Show the complete signature.) Use

`Employee`objects as keys in a`HashMap`

Keep a `SortedSet`of`Employee`objects

Be able to sort `Employee`objects by either their`name`field or their`EmployeeId`field

- (9 points) Suppose you have the following BNF rule:
**<foo> ::= "u" [ "x" ] | "w" { "y" }**

In the lists below, circle the`<foo>`s and cross out the non-`<foo>`s

`uu``uw``w``ux``uxy``wy``uxx``uxwy``wyyy`

- (4 points) Draw a state machine to recognize
`<foo>`objects, as defined in the previous question. Indicate which states are your start and final states. Do not include an error state.

- (3 points) Tell what the major error is in the following Recognizer method:
public boolean term() { if (!term()) return false; while (multiplyOperator()) { if (!term()) error("No term after '+' or '-'"); } return true; }

- (6 points) What order do you visit the nodes when you traverse this binary
tree:
- In preorder?

- In inorder?

- In postorder?

- In preorder?
- (3 points) What is the difference between a
**data type**and an**abstract data type**?

- (4 points) Assume that
`array`has been filled with randomly generated integers in the range 1 to 10. What is the expected running time (Big-O notation) of the following method?int findFive(final int ARRAY_SIZE, int[] array) { for (int i = 0; i < ARRAY_SIZE; i++) { if (array[i] == 5) return i; } return -1; }

- (4 points) What is the running time (Big-O notation) of the following method?
int log2(int n) { int result = 0; int power = 1; while (power < n) { result++; power = 2 * power; } return result; }

- (2 points) What is the difference between a
**mutative transformer**and an**applicative transformer**?

- (6 points) Suppose you wish to time a method. List
**three**ways to improve the accuracy of your timing.

- (4 points) Put the following in order, best to worst: O(n
^{2}), O(2^{n}), O(n), O(1), O(log n), O(n log n).

(best) (worst)

- (6 points) Suppose
`set1`and`set2`are both objects of type`Set`. For each of the following, write a single Java statement to:

- Make
`set1`the*union*of the two sets

- Make
`set1`the*intersection*of the two sets

- Make
`set1`the*difference*(`set1`-`set2`) of the two sets

- Set
`boolean isSubset`to`true`if and only if`set1`is a*subset*of`set2`

- Make
- (18 points) List
*three*methods declared by each of the following interfaces, with complete signatures. Do not include any inherited methods, for example,`equals`, or the methods that`SortedSet`inherits from`Set`.

Collection Set SortedSet List Map SortedMap

- (6 points) For each of the following sort methods, tell what the invariant
is. (An informal description in English is OK.)

Bubble sort Insertion sort Selection sort

- (3 points) What methods are required to implement each of the following
interfaces?

`Iterable`

`Comparable`

`Comparator`

- (8 points) State Dr. Dave's four rules for doing recursion.

- (4 points) From Joel on Software, by Joel Spolsky:

Schlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck.

The next day Schlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck.

The next day Schlemiel lpaints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?"

"I can't help it," says Schlemiel. "Every day I get farther and farther away from the paint can!"

Assuming that Schlemiel works continuously (not day by day) until the entire`N`yards of the road is painted, what is the running time in Big-O notation of*Schlemiel the Painter's Algorithm*?