CS 61B: Data Structures (Spring 2004)
Final Exam

### Solutions

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.

• Because each pass only collects garbage in one of the two spaces, it takes two passes to collect all the garbage, so this copying collector is no faster than the mark and sweep algorithm.
• The biggest object you can allocate is smaller.
c. The object referenced by y (and now by x) has its counter incremented. The object formerly referenced by x has its counter decremented.

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√nc bn for all nN,
which is equivalent to writing
√n log a ≤ log c + n log b for all nN,
which is equivalent to writing
log a / log b - log c / (√n log b) ≤ √n for all nN.
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
ab√n.
Raising both sides to the power of √n gives
a√nbn.
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);
```

Mail inquiries to cs61b@cory.eecs