Quiz 1: Questions

Q1.1.

[8 pts] Write a definition of the List interface as it would be defined within the java.util package, including at least four of the methods explicitly covered in class. Use the Java syntax for defining interfaces.

public interface List<E> {

Q1.2.

[12 pts] Below we have begun writing the ArrayList class as defined in lecture. Complete the add method. Your implementation should account for growing the array should the array already be full.

public class ArrayList<E> implements List<E> {
    private E[] contents;
    private int curSize;

    public boolean add(E value) {

Q1.3.

[10 pts] Draw a recursion tree corresponding to the invocation m(87) based on the recursive method listed below.

public static int m(int n) {
    if(n > 100) {
        return n - 10;
    } else {
        return m(m(n + 11));
    }
}

Below is a recursion tree corresponding to the invocation m(99) — but the recursion tree for m(87) is considerably larger.

Quiz 1: Solutions

Q1.1.

    public int size();
    public E get(int index);
    public E set(int index, E value);
    public boolean add(E value);
    public void add(int index, E value);
    public E remove(int index);
}

Q1.2.

        if(curSize == contents.length) {
            E[] newContents = (E[]) new Object[2 * contents.length];
            for(int i = 0; i < contents.length; i++) {
                newContents[i] = contents[i];
            }
            contents = newContents;
        }
        contents[curSize] = value;
        curSize++;
        return true;
    }
}

Q1.3.