Quiz 1

Problem 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> {

    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);
}

Problem 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) {

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

Problem 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.