CS240 Assignment 3 | Complete Solution

CS240 Assignment 3

Please read http://www.student.cs.uwaterloo.ca/~cs240/s15/guidelines.pdf for guidelines on submission. For the written problems, submit your solutions electronically as a PDF with le name a02wp.pdf using MarkUs. We will also accept individual question les named a02q1w.pdf, a02q2w.pdf, ... , a02q6w.pdf if you wish to submit questions as you complete them.

There are 44 marks available.
Problem 1 [5+4 = 9 marks]
a) Let R1; : : :Rn be n axis-aligned rectangles in the plane for which the corners are points in the n n-grid. Thus, for each rectangle Ri the four corners are points where both coordinates are integers in f1; : : : ng. Give an algorithm to sort R1; : : :Rn by increasing area in O(n) time.

b) 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.

Problem 4 [4 marks]
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.

Problem 5 [6 marks]
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

Problem 6 [12 marks]
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 x􀀀 and 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.