CIT 594 First Midterm Spring 2003, Dave Matuszek Name _______________________________________
1. (28 points) Assuming that A and B have the given values, evaluate each of the following:

 `A` `B` `(CAR A)` `(CAR B)` `(CONS A B)` `(APPEND A B)` `X` `Y` undefined `undefined` `(X . Y)` `undefined` `X` `(Y Z)` `undefined` `Y` `(X Y Z)` `undefined` `( )` `(Y Z)` ```undefined (also accepted: NIL)``` `Y` `(Y Z)` ```(NIL Y Z) or (( ) Y Z)``` `(X)` `(Y Z)` ` X` `Y` `((X) Y Z)` `(X Y Z)` `(X)` `( )` ` X` ``` undefined (also accepted: NIL)``` `((X))` `(X)` `( )` `( )` ```undefined (also accepted: NIL)``` ``` undefined (also accepted: NIL)``` `(( )) or (NIL)` `( ) or NIL` `(( ))` `Y` `( ) or NIL` `undefined` `((( )) . Y) or ((NIL) . Y)` `undefined or (NIL . Y)`
"Error" will be accepted anywhere the correct answer is "undefined."

2. (3 points) Evaluate: ```(EQUAL '(A B C) '(A . (B . (C . NIL))) )```          T

3. (3 points) Rewrite this S-expression with as few dots as possible: ```((A . B) . (C . NIL))```     ((A . B) C)
Note: The answer key that I created incorrectly had (A . B) . C). We will regrade this question.

4. (3 points) Diagram (with boxes and arrows) this S-expression: ```((A . B) . (C . NIL))```

5. (4 points) Assuming that the length of list `A` is `n` and the length of list `B` is `m`, give the Big-O running time of each of the following:
1. ```(CAR A)     O(1) ```
2. ```(CDR A)     O(1) ```
3. ```(CONS A B)     O(1) ```
4. `(APPEND A B)``     O(n)`

6. (5 points) Rules for writing recursive function in Lisp (fill in the blanks):

1. Unless the function is extremely simple, begin with a    COND   .

2. Test for a base case first—this usually means testing for   NULL   .

3. Avoid having more than one   base case   .

4. Do something with the    CAR   and recur with the    CDR   .

5. In each case of a `COND` you can use the fact that   all previous tests have returned false   .

7. (2 points) State, either in English or in logic notation, the loop invariant for the following code:

```for (int i = 0; i < array.length; i++) array[i] = 0;```

for all x < i, array[i] == 0    (OK to have   <=   instead of   <   ).
"All the array locations to the left of i have been set to zero."

8. (6 points) State, either in English or in logic notation, the loop invariant for the outer loop in each of the following:

1. Bubble sort
"Every element to the right (or left) of 'outer' (or 'the index,' or something like that) is in the correct place"
That is, for all j > outer, if i < j, then a[i] <= a[j]

2. Selection sort
"Every element to the left of the index (or 'outer') is in the correct place"
for all i <= outer, if i < j then a[i] <= a[j]

3. Insertion sort
"All elements to the left of the index (or 'outer') are sorted (or, relatively sorted)"
For all i < outer, j < outer, if i < j then a[i] <= a[j]

9. (5 points) Assume:
• A doubly-linked list is composed of nodes, defined as:
`class Node {int value; Node previous; Node next; }`
• `badNode` is a reference to a node in a doubly-linked list.
Write one or more lines of Java to delete `badNode` from the list it is in.

10. (4 points) List the names of all the methods in the `Iterator` interface, along with their parameter types and return types. Do not tell what each method does.

boolean hasNext()
Object next()
void remove()

11. (2 points) Name two methods in the `Arrays` class (`java.util.Arrays`). (Just names, please.)

Any two of: asList, binarySearch, equals, fill, sort

12. (5 points) Name five methods in the `Collection` interface.

Any five of: add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray

13. (6 points) Java uses two types of memory when the statement ```Vector v = new Vector(10)``` is executed. Name the two types and tell what is put into each type.

The variable v is put into the stack, the actual Vector object is put in the heap.

14. (3 points) What does the acronym DRY stand for?
Don't Repeat Yourself

15. (2 points) What is the distinction between prototype code and tracer code?
Prototype code is expected to be discarded; tracer code to be kept.

16. (2 points) What does it mean to say that two classes are "orthogonal"?

A change to one does not require a change to the other.

17. (2 points) What should you say when asked for an estimate of how long it will take to complete a new project?

"I'll get back to you."  (Or words to that effect.)

18. (2 points) Of the three sorting methods we studied--bubble sort, insertion sort, selection sort--which one would be preferable if we know the array is almost sorted, with just a few elements out of place?

Insertion sort.

19. (4 points) Name or describe four requirements that should be met when you override `equals`.

Reflexive: for any x, x.equals(x) should return true
Symmetric: for any non-null objects x and y, x.equals(y) should return the same result as y.equals(x)
Transitive: if x.equals(y) and y.equals(z) are true, then x.equals(z) should also be true
Consistent: x.equals(y) should always return the same answer

20. (2 points) What exactly does it mean to say that `compareTo` is consistent with `equals`?
x.compareTo(y)==0    gives the same boolean result as    x.equals(y)

21. (2 points) Name one advantage of bucket hashing over open hashing.

You never run out of room for new entries.
OR: Elements can be removed.

22. (5 points) Assume:
• class `Cell` is defined as ``` class Cell { int value; Cell next; }```,
• several `Cell`s are joined together to form a linked list,
• variable `first` is a reference to the first cell in the list
Write one or more lines of code to count the number of cells in the list.

int count = 0;
Cell here = first;
while (here != null) {
count++;
here = here.next;
}
OR
int count;
for (count = 0, Cell here = first; here != null; here = here.next) count++;