Final Exam

**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 *n*^{2} sin *n*,
or the function that is equal to *n*^{2} 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!

**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.

**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 `int`s 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(

which is equivalent to writinga≤^{√n}c bfor all^{n}n≥N,

which is equivalent to writing√nloga≤ logc+nlogbfor alln≥N,

logThis last statement is true if we choosea/ logb- logc/ (√nlogb) ≤√nfor alln≥N.

*Shorter but harder-to-think-of solution* (courtesy of Rohin Shah).
For all *n* greater than log_{b}^{2} *a*,

logRaising_{b}a≤√n.

Raising both sides to the power ofa≤b^{√n}.

If we choosea^{√n}≤b^{n}.

**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 ***k***th 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