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` ` ` ` ` ` ` ` ` `X` `(Y Z)` ` ` ` ` ` ` ` ` `( )` `(Y Z)` ` ` ` ` ` ` ` ` `(X)` `(Y Z)` ` ` ` ` ` ` ` ` `(X)` `( )` ` ` ` ` ` ` ` ` `( )` `( )` ` ` ` ` ` ` ` ` `(( ))` `Y` ` ` ` ` ` ` ` `

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

3. (3 points) Rewrite this S-expression with as few dots as possible: ```((A . B) . (C . NIL))```

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) ```
2. ```(CDR A) ```
3. ```(CONS A B) ```
4. `(APPEND A B)`

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

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

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

3. Avoid having more than one ________________________.

4. Do something with the __________________ and recur with the __________________.

5. In each case of a `COND` you can use the fact that ________________________.

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

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

2. Selection sort

3. Insertion sort

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.

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

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

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.

14. (3 points) What does the acronym DRY stand for?

15. (2 points) What is the distinction between prototype code and tracer code?

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

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

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?

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

20. (2 points) What exactly does it mean to say that `compareTo` is consistent with `equals`?

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

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.