CIT594 Midterm I

CIT 594 First Midterm
Spring 2003, Dave Matuszek

Name _______________________________________

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

(3 points) Evaluate: (EQUAL '(A B C) '(A . (B . (C . NIL))) ) T
(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.
(3 points) Diagram (with boxes and arrows) this S-expression: ((A . B) . (C . NIL))
(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)
(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 .
(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."
(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]
(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.

badNode.next.previous = badNode.previous;
badNode.previous.next = badNode.next; // order does not matter
(OK but unnecessary if they set badNode, badNode.next, badNode.previous to null.)
(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()
(2 points) Name two methods in the Arrays class (java.util.Arrays). (Just names, please.)

Any two of: asList, binarySearch, equals, fill, sort
(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
(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.
(3 points) What does the acronym DRY stand for?
Don't Repeat Yourself
(2 points) What is the distinction between prototype code and tracer code?
Prototype code is expected to be discarded; tracer code to be kept.
(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.
(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.)
(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.
(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
(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)
(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.
(5 points) Assume:
- class Cell is defined as class Cell { int value; Cell next; },
- several Cells 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++;