CS 61B: Data Structures
(Autumn 2006)
Final Exam
UNOFFICIAL Solutions
Problem 1. (9 points) A Miscellany.
Problem 2. (10 points) Sorting.
a. b. c.
See the official solution.
d.
Not sure why, but I think sortMe will not be sorted.
Problem 3. (9 points) Trees.
a.
4
/ \
2 6
/ / \
1 5 9
/ \
8 10
b.
At least 10 keys should be inserted. If we want to break two 3-key nodes, we must encounter them as parent-children. Assuming the parent 3-key node has three other 1-key children, the minimum number of insertions, counting the last insertion that breaks the two nodes, would be: 3 + 3 + 3*1 + 1 = 10.
Through trial-and-error, I found a sequence of 11 insertions that satisfy the requirements, namely 3 4 5 6 7 8 9 1 2 0 10, in that order. In other words, either my derivation above is wrong (should be at least 11 instead of 10), or there exists another example with 10 insertions only. Any input is greatly appreciated.
In the meantime, here's a few steps during those 11 insertions.
3 4 5 4 4 6 4 6 2 4 6
7 / \ 9 / | \ 2 / | \ 0 / | | \
-> 3 567 -> 3 5 789 -> 123 5 789 -> 01 3 5 789
Inserting 10 would then break the node 246 and 789
c.
if (no children): return the key since this is a leaf node
else: we keep track of a counter depth, which is set to 0 initially at the root.
if (depth is even):
return minimax(this.right, depth+1)
else:
return minimax(this.left, depth+1)
d.
A
/ \
B C
/ \ \
/ \ F
D E \
/ \ / J
G H I
/ \
K L
Preorder: A B D G H E I K L C F J
Postorder: G H D K L I E B J F C A
Problem 4. (9 points) Data Structures.
a.
a
Visited order, starting from a, is: a c g e b d f.
b.
For each vertex u, we need to find an edge incident on it by checking every other vertex w such that (u, w) (if u w), or (w, u) is in the hash table, and that we haven't visited w previously. Doing so, in the worst case, would take O(|V|2), which is much worse than the normal O(|V|+|E|) for DFS.
c.
Let's say you have N buckets, and n = N-1 items. The load factor is currently approaching 1. If you add two more items, you resize up. If you then remove two items, you resize down. Hence, a sequence of two add()s/remove()s would cause you to resize every now and then, and go bankrupt. Hence, the amortized running time of the two operations is not O(1).
d.
I believe this is similar to the derivation of randomized quicksort's running time in Lecture 38. We have a 1/2 chance of finding a good index, which we can then drop 1/4 of the items in the sorted array. Let D(n) be a random variable equal to the depth of an arbitrary key in a random n-index, retarded binary search. By the same derivation in Lecture 38,
E[D(n)] ≤ 2 log4/3 n.
Problem 5. (6 points) Dynamic Median Finding.
a.
When the number of elements is odd, return
- min key of min heap if size(min heap) > size(max heap)
- max key of max heap if size(min heap)
If the number of elements is even, return the max key of max heap, since every key of max heap is less than or equal to every key of min heap.
b.
- If the inserted key is bigger than or equal to the root of the min heap, insert it into the min heap.
- Else if the inserted key is smaller than or equal to the root of the max heap, insert it into the max heap.
- Otherwise (max(maxHeap) ), choose either heap arbitrarily and insert it into that heap.
c.
- If the inserted key is bigger than or equal to the root of the max heap, insert it into the min heap (max heap doesn't need it).
- Else (this new key absolutely needs to go into the max heap):
- Pop the max of the max heap via removeMax().
- Insert that popped key to the min heap - it will serve as the new root (minimum key) of the min heap.
- Insert the new key into the max heap.
Problem 6. (7 points) Binary Search Tree Insertion with Size and Height Fields.
public class BinaryTreeNode {
int key, size, height;
BinaryTreeNode parent, left, right;
// Constructor with key k, parent p.
public BinaryTreeNode(int k, BinaryTreeNode p) {
key = k; parent = p;
size = 1; height = 0; left = null; right = null;
}
// Inserts key k into "this" node's subtree; updates all sizes and heights.
public void insert(int k) {
if (k = b ? a:b;
}
}