CIT 594 Second Quiz Spring 2002, Dave Matuszek Name __________________________________________
1. (5 points each) True or false:

1. false   In Java, the length of an array is part of its type definition.

2. true    In Java, arrays are objects.

3. true    In Java, accessing an array element requires constant time.

4. true    The time complexity of an algorithm is usually more important than its space complexity.

5. true    Space complexity can be important in a doubly-recursive algorithm.

6. true    An operation `op` is reflexive if `op(x, x)` returns `true` for all `x`.

7. false   An operation `op` is transitive if, whenever` op(x, y)` is `true`,` op(y, x) `is also `true`.

8. true    A recursive and a non-recursive binary search have the same time complexity.

9. true    Certain data sets can make quicksort take O(n2) time.

10. false   In a doubly-linked list, every node has both a successor and a predecessor.

2. (5 points each) Give a brief definition (without examples) of each of the following terms:

1. reflective (when describing a data type)

The data type carries information about itself.

2. stable (when describing a sorting algorithm)

Equal elements retain their relative positions after sorting.

3. (8 points) A certain algorithm takes exactly 43n2+24n+17 time units. What is its time complexity?

O(n2)

4. (10 points) What does it mean to say that `compareTo` is consistent with equals ? (Be precise)

x.compareTo(y) == 0 gives the same boolean result as x.equals(y)
(This has nothing to do with the reflexive, symmetric, transitive restrictions on equals!)

5. (10 points) Rewrite the following list of functions in order of increasing Big-O complexity:
```n     n log n     63     n2     2n     n5     log n```

63     log n     n     n log n     n2     n5     2n
6. (12 points) Name (don't describe) the three kinds of nodes in a tree.

root, internal nodes, leaves