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?
`true`An`enum`is a class.`Yes, with methods and everything.``false`An`enum`may be`abstract`.`true`A tree that consists of a single node has depth zero.`false`If`for(Thing thing : things) {...}`is legal, then`things`is an`Iterator`.`No, it's an Iterable.``false`Strings in Java are terminated by a zero byte.`No, started with a length int.``false`A`hashCode()`method should return a number between 0 and the size of your array minus one.

Returns an int; hashCode() doesn't know the size of your array.`true`log_{2}1024 = 10.`false`If two algorithms have the same Big-O running time, they are equally fast.`true`If you implement equals, it should be reflexive, symmetric, and transitive.`false`It doesn't make sense for a class's only constructor to be private.`Used with Factory methods.`

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

`None``public boolean equals(Object o)`

public int hashCode()Keep a `SortedSet`of`Employee`objects

`Comparable (or use Comparator)``public int compareTo(T o)`

(Comparable uses public int compare(T o1, T o2) Be able to sort `Employee`objects by either their`name`field or their`EmployeeId`field

`None (but its Comparator must implement`public int compare(T o1, T o2) and public boolean equals(Object o) `None`

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

`Recursion is not with a simpler case.`while (multiplyOperator()) { if (!term()) error("No term after '+' or '-'"); } return true;`Also accepted: no base case, left recursive, infinite recursion`} - (6 points) What order do you visit the nodes when you traverse this binary
tree:
- In preorder?
`* + x y z`

- In inorder?
`x + y * z`

- In postorder?
`x y + z *`

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

`An abstract data type does not define the data representation.`

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

`O(1), or constant time; found on average after 5 probes.`} - (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;

`log`} return result; }_{2}(n) - (2 points) What is the difference between a
**mutative transformer**and an**applicative transformer**?

`A mutative transformer changes the given object; an applicative transformer returns a new object.`

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

`Any three of:`

Call System.gc() before doing the timing.

Minimize the number of other active processes.

Repeat the timing many times and take the average.

Repeat many times and discard the extreme values.

Use nanoTime() -- helps only on certain computers.

- (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) `O(1)``O(log n)``O(n)``O(n log n)``O(n`^{2})`O(2`^{n})(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

`set1.addAll(set2)`

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

`set1.retainAll(set2)`

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

`set1.removeAll(set2)`

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

`isSubset = set1.containsAll(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`.

`The following lists all and only the methods that I will accept for this question. All are public and abstract.`Collection `boolean add(E o)``Iterator<E> iterator()``boolean addAll(Collection<? extends E> c)``boolean remove(Object o)``void clear()``boolean removeAll(Collection<?> c)``boolean contains(Object o)``boolean retainAll(Collection<?> c)``boolean containsAll(Collection<?> c)``int size()``boolean equals(Object o)``Object[] toArray()``int hashCode()``<T> T[]`

toArray(T[] a)`boolean isEmpty()`Set `Just those declared in Collection.`SortedSet `Comparator<? super E> comparator()``SortedSet<E> headSet(E toElement``E first()``SortedSet<E> tailSet(E fromElement)``E last()``SortedSet<E> subSet(E fromElement, E toElement)`List `void add(int index, E element)``ListIterator<E> listIterator()``boolean addAll(int index, Collection<? extends E> c)``ListIterator<E> listIterator(int index)``E get(int index)``E remove(int index)``int indexOf(Object o)``E set(int index, E element)``int lastIndexOf(Object o)``List<E> subList(int fromIndex, int toIndex)`Map `void clear()``boolean isEmpty()``boolean containsKey(Object key)``Set<K> keySet()``boolean containsValue(Object value)``V put(K key, V value)``Set<Map.Entry<K,V>> entrySet()``void putAll(Map<? extends K,? extends V> t)``boolean equals(Object o)``V remove(Object key)``V get(Object key)``int size()``int hashCode()``Collection<V> values()`SortedMap `Comparator<? super K> comparator()``K lastKey()``K firstKey()``SortedMap<K,V> subMap(K fromKey, K toKey)``SortedMap<K,V> headMap(K toKey)``SortedMap<K,V> tailMap(K fromKey)`

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

Bubble sort `Everything on the right end of the array is in the correct place.`

for all j > outer, if i < j, then a[i] <= a[j]Insertion sort `All elements on the left end of the array are sorted with respect to one another`

For all i < outer, j < outer, if i < j then a[i] <= a[j]

Selection sort `Everything on the left end of the array is in the correct place.`

for all i <= outer, if i < j then a[i] <= a[j]

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

`Iterable``Iterator<T> iterator()`

`Comparable``int compareTo(T o)`

`Comparator``int compare(T o1, T o2)`

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

`Do the base cases first`

Recur only with a simpler case

Don't modify and use nonlocal variables

Don't look down

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

`At each step, Schlemiel goes to the paint can and back (an average of distance of N) and paints some constant number of dots (say, one yard's worth). He must do this N times. Hence, O(N`^{2}).

`For an exhaustive discussion, see:`

http://discuss.fogcreek.com/techInterview/default.asp?cmd=show&ixPost=153