Exam 2: Questions

X2.1.

[8 pts] Give an invariant for the below loop that allows for the conclusion that after the loop, the ArrayList a contains no adjacent duplicates.

int i = 1;
while(i < a.size()) {
    if(a.get(i).equals(a.get(i - 1))) {
        a.remove(i);
    } else {
        i++;
    }
}

X2.2.

[8 pts] In terms of n, how much time does the code fragment at right take? Give your answer using Big-O notation, with the tightest and simplest bound possible. Justify your answer.

int i = 0;
int j = 1;
while(j < n) {
    i++;
    if(i == n) {
        j *= 2;
        i = 0;
    }
}

X2.3.

[4 pts] Write the in-order traversal of the below tree.

X2.4.

[10 pts] We have started to write an implementation of the Set interface below using a binary search tree. Complete the contains method.

public class BstSet<E> implements Set<E> {
    private TreeNode<E> root;
    private int curSize;

    public BstSet() { root = null; curSize = 0; }

    public boolean contains(E value) {

X2.5.

[10 pts] Suppose we are implementing the Map interface using a hash table. Describe step-by-step in detail how the get method would work.

X2.6.

[8 pts] Explain why we say that HashMap's get method takes O(1) time.

X2.7.

[8 pts] Suppose we have a class PhoneNumber class for representing phone numbers. Each instance has int instance variables, exch for the 3-digit exchange and ext for the 4-digit extension. For example, the number 450-1377 has an exchange of 450 with an extension of 1377.

Critique each of the following hashCode methods.

a.	int hashCode() { return exch; }
b.	static Random rand = new Random(); int hashCode() { // returns random integer from -2^31 to 2^31-1 return rand.nextInt(); }

X2.8.

[8 pts] Describe how the Stack and Queue ADTs are functionally different.

X2.9.

[8 pts] How can the Queue ADT be implemented so that both add and remove take O(1) time using an array to hold the queue's elements?

X2.10.

[8 pts] Suppose that Comparable is an interface and Integer is an implementation of that interface. Suppose, moreover, that ZERO is an Integer constant defined within the class we are writing.

For each of the following fragments, would it compile as written? (At least one of them would.) For each of the other(s), explain how you could repair it so it would compile.

boolean isNeg(Comparable a) {
    return a.compareTo(ZERO) < 0;
}

void run() {
    Comparable a = new Comparable(0);
    System.out.println(isNeg(a));
}

boolean isNeg(Comparable a) {
    return a.compareTo(ZERO) < 0;
}

void run() {
    Comparable a = new Integer(0);
    System.out.println(isNeg(a));
}

boolean isNeg(Integer a) {
    return a.compareTo(ZERO) < 0;
}

void run() {
    Comparable a = new Comparable(0);
    System.out.println(isNeg(a));
}

boolean isNeg(Integer a) {
    return a.compareTo(ZERO) < 0;
}

void run() {
    Comparable a = new Integer(0);
    System.out.println(isNeg(a));
}

Exam 2: Solutions

X2.1.

There are no adjacent duplicates among the first i elements of a.

X2.2.

O(n log n). Every n iterations of this loop, i finally reaches n and then j doubles. Starting from 1, j can double itself 1 + log n times before reaching 2^1 + log n = 2 n. Thus, there are at most n log n iterations, and each iteration takes O(1) time, for a total of O(n log n) time.

X2.3.

d b h e a f i c g

X2.4.

        Comparable<E> comp = (Comparable<E>) value;
        TreeNode<E> n = root;
        while(n != null) {
            int c = comp.compareTo(n.getValue());
            if(c < 0) {
                n = n.getLeft();
            } else if(c > 0) {
                n = n.getRight();
            } else {
                return true;
            }
        }
        return false;
    }

X2.5.

It applies the hashCode method to the requested key and maps this int into a valid array index by finding the remainder of dividing the hash code by the array length.
It goes to that array index to find the first entry of a bucket. It steps through each entry of the bucket until it finds an entry whose key matches the requested key.
If it finds such an entry, it returns the value stored within that entry; and if it doesn't find such an entry, the method returns null.

X2.6.

The hashCode method is generally quite quick, and certainly independent of the number of things in the map, so it makes sense to say that mapping the requested key to an array index takes O(1) time.

The get method must also step through each entry in its bucket. A reasonably good hashCode method will distribute the keys largely evenly among the buckets, and the HashMap class is written so that the average bucket length is 0.75. (It doubles the array length whenever the average bucket length exceeds 0.75). As a result, we end up stepping through only 0.75 entries in the bucket, on average.

X2.7.

a. This method leads to many collisions if we have several telephone numbers in the same exchange, as is likely if we are storing telephone numbers from the same town.

b. This method returns a different value each time it is invoked. Consequently, if we use hashCode to add a value into a HashSet and we later use contains on the same value, we'll get a different hash code, and so the HashSet will look in a different bucket than when the value was stored.

X2.8.

With a stack, additions and removals both occur at the same end of a list of stored elements. With a queue, they occur on opposite ends.

X2.9.

We use a circular buffer, where both the front and the rear of the queue shift — the rear index shifts on an add, and the front index shifts on a remove. When either goes off the end of the array, it wraps around back to index 0.

X2.10.

a. This is illegal because it is not legal to create an instance of an interface as in new Comparable(0).

b. This is legal.

c. This is illegal because it is not legal to create an instance of an interface as in new Comparable(0). Moreover, we cannot pass a Comparable as an argument to a method that expects an Integer parameter.

d. This is illegal because we cannot pass a Comparable as an argument to a method that expects an Integer parameter.