[14 pts] Write a class definition Interval for representing an interval of numbers. The class should incorporate the following methods.

Interval(double a, double b)

(Constructor) Constructs an object representing the range of numbers between a and b, inclusive. The constructor may assume that a < b.

void add(double x)

Extends this interval, if necessary, so that x is included within this interval.

boolean contains(double q)

Returns true if this interval contains the number q.

The below program fragment illustrates how a different class might use the class you write.

Interval range = new Interval(4, 10);
System.out.println(range.contains(2)); // says false
System.out.println(range.contains(4)); // says true
System.out.println(range.contains(6)); // says true
range.add(2);
System.out.println(range.contains(1)); // says false
System.out.println(range.contains(2)); // says true
System.out.println(range.contains(3)); // says true

[10 pts] Suppose we define f as at below. At right, draw a recursion tree diagramming the computation of f(23).

    public static int f(int n) {
        if(n % 2 == 0 || n == 1) {
            return 1;
        } else {
            int a = f((n - 1) / 2);
            int b = f((n + 1) / 2);
            return a + b;
        }
    }

Also, what value is returned by f(23)?

[10 pts] Recall the ListNode class we studied.

public class ListNode<E> {
    private E value;
    private ListNode<E> next;

    public ListNode(E v, ListNode<E> n) { val = v; next = n; }
    public E getValue() { return val; }
    public ListNode<E> getNext() { return next; }
    public void setValue(E v) { value = v; }
    public void setNext(ListNode<E> n) { next = n; }
}

Suppose we've begun to implement a class using a singly linked list as below. Complete the size method to return the number of entries in the list.

public class SinglyLinkedList<E> {
    private ListNode<E> head;
    // no more instance variables!

    public SinglyLinkedList() {
        head = null;
    }

    public int size() {

[10 pts] Continuing the SinglyLinkedList class of the previous problem, complete the add method to add a value at the end of the list. (Again, no more instance variables.)

      public void add(E value) {

[8 pts] Consider the below method.

    public static void mystery(List names) {
        Iterator it = names.iterator();
        while(it.hasNext()) {
            if(it.next().startsWith("p")) {
                System.out.println(it.next());
            }
        }
    }

What would this method display if invoked with the parameter being a LinkedList holding the below strings?

[8 pts] Explain why an Iterator is preferable for iterating through the elements over a LinkedList (rather than successively invoking LinkedList's get method for each index).

[12 pts] Give an invariant for the following loop that allows for the conclusion that after the loop, sum is ∑_j = 1ⁿ j². the sum of the squares from 1 to n.

int sum = 0;
int i = 0;
int i2 = 0;
while(i != n) {
    i2 = i2 + i + i + 1;
    i = i + 1;
    sum += i2;
}

Suppose that k represents the value of i at the beginning of one iteration, and suppose that your invariant holds for that instant. Argue for why your invariant will still be true at the end of that iteration.

[8 pts] The below loop starts with an array nums of ints. Give an invariant for the following loop that allows for the conclusion that after the loop, there is an index k in the array data where for all indices i ≤ k, nums[i] ≤ nums[0], and for all indices i > k, nums[i] ≥ nums[0].

int a = 1;
int b = nums.length - 1;
while(a + 1 != b) {
    if(nums[a] <= nums[0]) {
        a++;
    } else if(nums[b] >= nums[0]) {
        b--;
    } else {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
        a++;
        b--;
    }
}