Answer: It means that there exists a k and an m such that the space required by MergeSort to sort an array of length p, for p > m, is ≤ kp
Answer:
Data structure Main advantage(s) Main disadvantages
Resizable array
Index to any position in O(1) time
Inserting requires O(n) time to shift elements;
growing array requires O(n) time to copy elements
Linked list
Insert/remove in O(1) time if iterator points to place to insert/remove
O(n) time to access nth element if starting from front of list
Tree
O(log n) find/insert/remove if a balanced search tree; excellent guaranteed performance
Lookup not quite as fast as a good hash table
Hash table
O(1) time (great!) to lookup data associated with a key, if the hash function is good;
generally excellent insert/lookup performance
Lookup time degrades badly, to as bad as O(n), if the hash table has lots of collisions;
good insert/lookup performance is not guaranteed
Answer: Apply the hash function to the key (using O(1) time) to get an index into the hash table. That index points to a linked list (or other data structure); search that (hopefully short) linked list sequentially to find the key/data pair for the searched-for key.
Answer: Do a binary search on the binary search tree to find the key (taking at most O(log n) time), and its associated data.
Answer: TreeMap provides O(log n) guaranteed find/insert/remove; use TreeMap if you need a guarantee of no worse than O(log n). HashMap generally provides O(1) find/insert/remove, but can degrade to poor performance if the hash function has many collisions; use HashMap if you want excellent performance most of the time and you believe that you can control the hash function and data to avoid frequent collisions.
Answer: Tree is best because it can keep the data in a sorted form that allows fast lookup/insert/remove.
Answer: Indexing into the List takes O(1) time in a contiguous implementation but O(n) time in a non-contiguous implementation.
What is the main advantage of a non-contiguous implementation of a List over a contiguous implementation?
Answer: If you are iterating through the non-contiguous implementation, you can insert or remove an element at the iteration point in O(1) time, while doing so in the contiguous implementation takes (in general) O(n) time.
If resizable array X has m elements:
If linked list X has m elements:
If binary tree X has m elements:
If hash table X has m elements:
P(0) = P(1) = P(2) = 1
P(n) = P(n-2) + P(n-3) for n > 2
Write a recursive method that returns the nth Padovan number.
Answer:
int P(int n) {
if (n <= 2) {
return 1;
} else {
return P(n-2) + P(n-3);
}
}
A(0, n) = n + 1
A(m, 0) = A(m-1, 1) if m > 0
A(m, n) = A(m-1, A(m, n-1)) if m > 0 and n > 0
Write a recursive method that computes Ackermann(m, n) for any positive integers m and n.
Answer:
int A(int m, int n) {
if (m == 0) {
return n + 1;
} else if (n == 0) {
return A(m-1, 1);
} else {
return A(m-1, A(m, n-1))
}
{
Aside: you might enjoy figuring out how quickly Ackermann's function grows:
just A(4, 2) requires 19,729 decimal digits!!!
class Node {
E element;
Node next;
}
class Node {
E element;
Node next;
}
Write a recursive method add(E e) in the Node class
that adds the given element to the end of the linked list. Note that this method
is a member of the Node class; you do not need to deal with an empty linked list
in this problem.
Answer:
private void add(E e) {
if (this.next == null) {
this.next = new Node(element);
} else {
this.next.add(e);
}
}
private E get(int n) {
if (n == 0) {
return this.element;
} else {
return this.next.get(n - 1);
}
}
class TernaryTreeNode {
E data;
TernaryTreeNode left;
TernaryTreeNode middle;
TernaryTreeNode right;
}
Write a recursive method in the TernaryTreeNode class that prints
the data on the rightmost branch (root to leaf) of the tree,
with the root first and the leaf last.
Answer:
private void print() {
System.out.println(this.data);
if (this.right != null) {
this.right.print();
}
}
private void print() {
if (this.right != null) {
this.right.print();
}
System.out.println(this.data);
}
private int countNulls() {
int count = 0;
if (this.data == null) {
count = 1;
}
if (this.left != null) {
count += this.left.countNulls();
}
if (this.middle != null) {
count += this.middle.countNulls();
}
if (this.right != null) {
count += this.right.countNulls();
}
return count;
}
private int find(int k, int[] x) {
return find(int k, int[x], 0, x.length - 1);
}
private int find(int k, int[] x, int begin, int end) {
if (begin > end)
return -1;
} else {
int middle = (begin + end) / 2;
if (k < x[middle]) {
return find(k, x, begin, middle - 1);
} else if (k > x[middle]) {
return find(k, x, middle + 1, end);
} else {
return middle;
}
}
}
if the array has 1 element, return.
MergeSort the left half of the array.
MergeSort the right half of the array.
Merge the two halves.
Iterate through the data in some order.
- If you find K, return the current index.
- If you get through all the data without finding K, return -1.
Best-case run-time means the best run-time of all instances of size N, where N is the size of the problem under consideration.
Average-case run-time means the run-time, averaged over all instances of size N, where N is the size of the problem under consideration. Note that this requires a probability distribution on instances of size N -- unless specified otherwise, we usually assume that all instances are equally likely (even though this assumption is unlikely to be valid in practice).
1. Traverse X to find the smallest element in X. Put that smallest element into X[0].
2. Repeat step 1 to find the 2nd smallest (putting it into X[1]).
3. Repeat step 1 to find the 3rd smallest (putting it into X[2]).
4. Etc until all N elements are done.
Be able to explain your answers to the following:
1. If start >= end, stop (the array is sorted in the range from start to end). Otherwise:
2. Recursively MergeSort the left half of X (from start to the middle).
Recursively MergeSort the right half of X (from middle to end).
3. Merge the two sorted halves [as described in class].
Be able to explain your answers to the following:
1. If start >= end, stop (the array is sorted in the range from start to end). Otherwise:
2. Let Pivot = X[start].
For k from start + 1 to end:
-- If X[k] <= Pivot, copy X[k] into the next spot of temporary array called LessThanPivot.
-- If X[k] > Pivot, copy X[k] into the next spot of temporary array called MoreThanPivot.
3. Recursively QuickSort LessThanPivot.
Recursively QuickSort MoreThanPivot.
4. Copy the sorted LessThanPivot into X,
then put Pivot into the next position in X,
then copy the sorted MoreThanPivot into the remaining positions in X.
Be able to explain your answers to the following:
Total: 130 points (but the exam will cover only 100 of the above 130 points, i.e., some topics will not show up on the exam)