Midterm Review

Question 1

Which of the JCF interfaces would be the most useful if we want to store a collection of students
enrolled in COMP2402 so that we can quickly check if a student is enrolled in COMP2402?

Answer 1

Set

Question 2

What if we also want to be able to quickly output a list of students, sorted by (lastname,firstname)?

Answer 2

SortedSet

Question 3

What if, in addition, we also want to store some auxiliary information (e.g., a mark) with each student?

Answer 3

SortedMap

Question 4

A Bag is like a Set except that equal elements can be stored more than once. Which of the following
is best suited to implement a Bag<T>?</T>

Answer 4

b or c depending on behaviour

Question 5

The running time of the methods get(i) and remove(i) for an ArrayList are?

Answer 5

O(1) and O(1 + size() − i), respectively

Question 6

The running time of the methods get(i) and remove(i) for a LinkedList are?

Answer 6

O(1 + min{i, size() − i}) and O(1 + min{i, size() − i}), respectively

Question 7

public static void insertAtBack(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.add(new Integer(i));
}
}
The above method is</Integer>

Answer 7

about the same speed independent of whether l is an ArrayList or a LinkedList

Question 7

public static void frontGets(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.get(0);
}
}
The above method is</Integer>

Answer 7

about the same speed independent of whether l is an ArrayList or a LinkedList

Question 7

public static void randomGets(List<Integer> l, int n) {
Random gen = new Random();
for (int i = 0; i < n; i++) {
l.get(gen.nextInt(l.size()));
}
}
The above method is</Integer>

Answer 7

much faster when l is an ArrayList

Question 8

public static void insertAtFront(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.add(0, new Integer(i));
}
}
The above method is</Integer>

Answer 8

much faster when l is a LinkedList

Question 8

public static void insertInMiddle(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.add(new Integer(i));
}
for (int i = 0; i < n; i++) {
l.add(n/2+i, new Integer(i));
}
}
The above method is</Integer>

Answer 8

about the same speed independent of whether l is an ArrayList or a LinkedList

Question 9

public static void insertInMiddle2(List<Integer> l, int n) {
for (int i = 0; i < n; i++) {
l.add(new Integer(i));
}
ListIterator<Integer> li = l.listIterator(n/2);
for (int i = 0; i < n; i++) {
li.add(new Integer(i));
}
}
The above method is</Integer></Integer>

Answer 9

much faster when l is a LinkedList

Question 9

Recall that an ArrayStack stores n elements in a backing array a at locations a[0],. . . ,a[n-1]:
public class ArrayStack<T> extends AbstractList<T> {
T[] a;
int n;
...
}
Also recall that, immediately after the backing array a is resized by grow() or shrink it has a.length =
2n.
When adding an element, the ArrayStack grows the backing array a if it is full, i.e, if a.length = n.
If are currently about to grow the backing array a, what can you say about the number of add() and
remove() operations (as a function of the current value of n) since the last time the ArrayStack was
resized?</T></T>

Answer 9

At least n/2 add() operations have occurred since then

Question 10

From the previous two questions, what can you conclude about the total number of elements copied
by grow() and shrink() if we start with an empty ArrayStack and perform m add() and remove
operations.

Answer 10

At most 2m elements are copied by grow() and shrink()

Question 10

Recall that we shrink the backing array a when 3n < a.length. If we are currently about to shrink
the backing array a, what can you say about the number of add() and remove() operations since the
last time the ArrayStack was resized?

Answer 10

At least n/2 remove() operations have occurred since then

Question 10

Recall that an ArrayDeque stores n elements at locations a[j], a[(j+1)%a.length],. . . ,a[(j+n-1)%a.length]:
public class ArrayDeque<T> extends AbstractList<T> {
T[] a;
int j;
int n;
...
}
What is the amortized running time of the add(i,x) and remove(i) operations?</T></T>

Answer 10

O(1 + min{i, n − i})

Question 11

Recall that a DualArrayDeque implements the List interface using two ArrayStacks:
public class DualArrayDeque<T> extends AbstractList<T> {
ArrayStack<T> front;
ArrayStack<T> back;
...
}
In order to implement get(i) we need to get it from the ArrayStack, front or back. We can express
this as</T></T></T></T>

Answer 11

Either (b) or (c) depending on the value of i and front.size()

Question 12

If a RootishArrayStack has 10 blocks (so b.size() = 10), then how many elements can it store?

Answer 12

55

Question 13

In a RootishArrayStack, a call to get(13) will return

Answer 13

blocks.get(4)[3]

Question 14

Recall our implementation of a singly-linked list (SLList):
protected class Node {
T x;
Node next;
}
public class SLList<T> extends AbstractList<T> {
Node head;
Node tail;
int n;
...
}
Consider how to implement a Queue as an SLList. When we enqueue (add(x)) an element, where
does it go? When we dequeue (remove()) an element, where does it come from?</T></T>

Answer 14

We enqueue (add(x)) at the tail and we dequeue (remove()) at the head

Question 15

Consider how to implement a Stack as an SLList. When we push an element where does it go? When
we pop an element where does it come from?

Answer 15

We push at the head and we pop at the head

Question 16

Using the best method you can think of, how quickly can we find the ith node in an SLList?

Answer 16

in O(1 + min{i, n · (n − i − 1)}) time

Question 17

Recall our implementation of a doubly-linked list (DLList):
protected class Node {
Node next, prev;
T x;
}
public class DLList<T> extends AbstractSequentialList<T> {
protected Node dummy;
protected int n;
...
}
6
Explain the role of the dummy node. In particular, if our list is non-empty, then what are dummy.next
and dummy.prev?</T></T>

Answer 17

dummy.next is the first node in the list and dummy.prev is the last node in the list

Question 18

Consider the correctness of the following two methods that add a node u before the node p in a DLList.
protected Node add(Node u, Node p) {
u.next = p;
u.prev = p.prev;
u.next.prev = u;
u.prev.next = u;
n++;
return u;
}
protected Node add(Node u, Node p) {
u.next = p;
u.next.prev = u;
u.prev = p.prev;
u.prev.next = u;
n++;
return u;
}

Answer 18

first method

Question 19

What is the running-time of add(i,x) and remove(i) in a DLList?

Answer 19

O(1 + min{i, size() − i}) and O(1 + min{i, size() − i}), respectively