*printable version*
# Exam 1

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]

### Problem X1.1.

[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

public class Interval {
private double lo;
private double hi;
public Interval(double a, double b) {
lo = a;
hi = b;
}
public void add(double x) {
if(x < lo) lo = x;
if(x > hi) hi = x;
}
public boolean contains(double q) {
return lo <= x && x <= hi;
}
}

### Problem X1.2.

[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)`

?

The method returns 5.

### Problem X1.3.

[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() {

int count = 0;
ListNode<E> n = head;
while(n != null) {
count++;
n = n.getNext();
}
return count;
}

### Problem X1.4.

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

if(head == null) {
head = new ListNode<E>(value, null);
} else {
ListNode<E> n = head;
while(n.getNext() != null) {
n = n.getNext();
}
n.setNext(new ListNode<E>(value, null));
}
}

### Problem X1.5.

[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?

*peter*,
*piper*,
*picked*,
*a*,
*profuse*,
*peck*,
*of*,
*pickled*,
*peppers*
### Problem X1.6.

[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).

It is faster. Using the `get`

method many times, each
`get`

for an element
near the middle of the LinkedList will force the LinkedList to
scan through nearly half the list to find the requested
element. The Iterator, however, will remember

its
current location in the list, and each step to the following
element will not require scanning.

### Problem X1.7.

[12 pts]
Give an invariant for the following loop that allows for the
conclusion that after the loop, `sum`

is
∑_{j = 1}^{n} `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.

The invariant is:

`i2`

is `i`

² and
`sum`

is
∑_{j = 1}^{i} `j`²

We suppose the invariant holds at the beginning of some iteration when
`k` represents the value of `i`

; thus, we
suppose that
`i2`

is `k`² and
`sum`

is
∑_{j = 1}^{k} `j`²
at the beginning of the iteration.
By the end of the iteration, `i`

becomes
`k` + 1, and so we need to argue that
`i2`

is (`k` + 1)² and
`sum`

is
∑_{j = 1}^{k + 1} `j`²
at the end of the iteration.
During the iteration, `i2`

changes to
2`k` + 1 more than the old value of
`i2`

, which was
`k`²;
thus, `i2`

becomes
`k`² + 2`k` + 1
= (`k` + 1)², which is the first
half of what we want to show.
Also during the iteration, `sum`

increases by the new
value of `i2`

, which we just showed is
(`k` + 1)².
Thus, after the iteration completes, `sum`

is
∑_{j = 1}^{k} `j`² + (`k` + 1)²
=
∑_{j = 1}^{k + 1} `j`²,
which is the second half of what we want to show.

### Problem X1.8.

[8 pts]
The below loop starts with an array `nums`

of `int`

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

For all indices
`i`

< `a`,
`nums[i]`

≤ `nums[0]`

,
and for all indices
`i`

> `b`,
`nums[i]`

≥ `nums[0]`

.