1. Is it possible to sort a set of n circles (instead of rectangles), by area, in linear time, using a similar argument as Part(a)? For that, we assume centers are point in the n n-grid and radii are integers bounded by n. Briey justify your answer.
Problem 2 [ 5 marks] Let X = f x1; : : : ; xn g be a set of n integers, satisfying xi n3 for all i, 1 i n. Describe an O(n) time algorithm that nds the minimal absolute value of the di erence between
elements of xi. That is, we are looking for some pair xi; xj such that xi xj is closest to 0.
Problem 3 [2+4+2=8 marks]
We denote by leftheight(u) and rightheight(u) the heights of the left and the right subtrees of a node u. Which of the following trees must be of height O(log n)? Show your work.
a) There is a constant c > 0 such that for all nodes u in a tree T1 leftheight(u) rightheight(u) + c.
b) There is a constant c > 0 such that for all nodes u in a tree T2, leftheight(u) c rightheight(u) leftheight(u) + c.
c) Every internal node u in a tree T3 has exactly two children.
In this question we assume that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key n. Estimate the largest possible number of nodes in T. Provide as exact estimate as possible.
Describe a data structure that supports the following operations in O(log n) time:
- search(x) nds the element with key x
- insert(x) and delete(x) insert and remove an element with a key x
- deleteLast() removes the most recently inserted element
Show how the B+-tree with M = 3 can be extended to support the oracle queries de ned below. In this question we assume that the data structure is static and it is not necessary to update the B+-tree. Recall that all key-value pairs are stored in the leaves of the B+-tree. Internal nodes contain copies of keys stored in the leaves. We assume for simplicity that an internal node with d children holds d keys; the i-th key stored in the node u is the smallest key stored in the i-th child of u. See Fig. 1 for an example.
12 21 24 31 43 49 51 57 62 67 79 81 82
12 21 24 43 51 57 62 67 79 82
12 43 57 79
12 57
Figure 1: Example of a B+-tree. In an oracle query osearch(x; ef ), we are given a pointer to a leaf that holds the key ef > x and we search for the key x. Let x denote the largest key stored in the tree that is smaller than x. Let df denote the number of elements between xand ef ; if x is smaller than all keys in the tree, then df is the total number of keys that do not exceed ef . Describe an algorithm that answers queries osearch(x; f) in O(log df ) time. That is, the time to answer a query osearch(x; f) must be logarithmic in the number of elements between ef and x.
Hint: You need to augment the B+-tree with additional pointers stored in nodes of the
B+-tree.