Problem 1. (5 points) Quickies.
b. Here are several examples: n log log n; n √(log n); n α(n, n) where α is the inverse Ackermann function. Another approach is to use a function that oscillates between large and small, such as n2 sin n, or the function that is equal to n2 for even n and zero for odd n.
c. 4 6 7 2 ^ ^ + 3 1 * +
d.
Iterating Iterating Iterating Except my apologies I'm final java.lang.Exception: Wrong!Problem 2. (8 points) Garbage Collection.
a. It allows you to use 2/3 of your computer's memory; not just half.
b.There are two good answers here.
d. Objects that reference themselves, or groups of objects that reference each other in a cycle (like listnodes in a doubly-linked list), will not be garbage collected even if they are no longer live.
Problem 3. (5 points) Sorting.
a.
7 8 9 3 4 2 1 0
0 8 9 7 4 2 3 1
0 1 9 7 4 8 3 2
0 1 2 7 9 8 4 3
0 1 2 3 9 8 7 4
0 1 2 3 4 8 9 7
0 1 2 3 4 7 9 8
0 1 2 3 4 7 8 9
b. Radix sort the 100 different values using one copy of each value, yielding a sorted array that maps the numbers 0…99 to the 100 different values. Use a hash table to map the 100 sorted values back to their indices 0…99. Sort the one billion ints by using counting sort, where the hash table maps each int to a bucket in the range 0…99.
Problem 4. (7 points) Search Trees.
a.
2
2
8
/
\
/ \
/
1
3
1 8
2
\
/
/ \
4
4
1 4
\
/ \
/ \
8
3 6
3 6
/
/
/
6
5
5
/
5
b. Create a root node whose item is the item at index f(n). (We assume the array is indexed from zero.) Recursively build complete trees for the subarray to the left of this item, which becomes the left child of the root node, and for the subarray to the right, which becomes the right child of the root node.
c. The stack implementation keeps a counter. To push an item, increment the counter and store the item in the 2-3-4 tree with the counter value as its key. To pop an item, find the item in the tree with the maximum key, remove it, and return it.
Problem 5. (8 points) Disjoint Sets.
a.
b. Seven. Perform a find operation on each of the seven leaves that are not already a child of the root.
c.
d. Give every node a prevSibling reference. Siblings are now doubly-linked, so a node can be removed from the list of its parent's children in constant time.
Problem 6. (5 points) Asymptotic Analysis.
The big-Oh notation a√n ∈ O(bn) means that there exist numbers c > 0 and N such that
a√n ≤ c bn for all n ≥ N,which is equivalent to writing
√n log a ≤ log c + n log b for all n ≥ N,which is equivalent to writing
log a / log b - log c / (√n log b) ≤ √n for all n ≥ N.This last statement is true if we choose c ≥ 1 and N ≥ (log a / log b)2. Therefore, a√n ∈ O(bn).
Shorter but harder-to-think-of solution (courtesy of Rohin Shah). For all n greater than logb2 a,
logb a ≤ √n.Raising b to the power of both sides gives
a ≤ b√n.Raising both sides to the power of √n gives
a√n ≤ bn.If we choose c ≥ 1 and N ≥ logb2 a, we prove a√n ∈ O(bn).
Problem 7. (5 points) Amortized Analysis.
a. ⌈ √ n ⌉ - 1.
b.
c. Compute the sum of all the resizing operations, add an additional n dollars for the n insert operations, and take the average by dividing the total by n.
Problem 8. (7 points) Finding the kth Item in a Preorder Tree Traversal.
if (k > size) {
return null;
}
if (k == 1) {
return element;
}
if (leftChild == null) {
return rightChild.elementAt(k - 1);
}
if (k <= leftchild.size + 1) {
return leftChild.elementAt(k - 1);
}
return rightChild.elementAt(k - 1 - leftChild.size);