Tree insertion sort We can sort n objects in O(n log n) unit operations as follows: We first initialize an empty binary search tree T. We second insert each of the n elements into T in turn. We third traverse the tree T and output the n elements in T using an in-order traversal. If we can insert an element into the tree in O(log |T) time, where |T| denotes the size of the tree, then our sorting algorithm will run in time O(n log n). There are several binary search trees in which basic operations can be done in time O(log |T]), such as red-black trees, AVL trees, and B-trees, which enables e.g. sorting in O(n logn). For the purposes of this assignment, we can mostly think of such a tree as an array, but where all standard operations take time O(log |T]). Let us define T[j] to denote the ith smallest element in T. In such trees, we can conduct a search in time O(log |T]), no matter which variant it may be, including e.g. "find the largest index j for which T[j] x," "find the largest index j for which T[j] < x," "find the smallest index j for which T[j] > x," "find the smallest index j for which T[j] x." Let A [11, 3, 2, 7, 13, 5, 9, 4, 12, 1] be an unsorted array of n = 10 elements which we sort using the above tree insertion method. After one insertion, our tree is T = [11]. After two insertions, our tree is T = [3, 11]. After six insertions, our tree is T = [2, 3, 5, 7, 11, 13]. Note that the sixth element A[6] = 5 is inserted at index 3. - Dominating points in the plane Now for the first application of insertion sorting. We are given n points pi = plane. Here is an example of eight points. Y .4 .2 .3 .1 .7 .6 = X We say a point p (a, b) dominates a point q = (a', b') if a a' and b b' and p q. If p dominates 9, then we say that (p, q) is a dominating pair. In the example, point 4 dominates the three points {1,2,3}, and point 6 dominates the two points {1,5}. The example contains 21 dominating pair. 1. Fill in the remaining six number of points each point dominates in the first line in the table shown below. 1 Number of points dominating: Inserted at index (key is (y, x)): 1 2 3 4 3 5 =(x, y) in the 6 2 7 8 8 2. We now insert the eight points into an initial binary search tree as discussed above, in turn, in the order they are labeled above, and as we insert each point, we note the index at which the point is being inserted. We insert a point with respect to key (y,x). That is, for points (a, b) and (a', b'), then (a, b) > (a', b') if b> b' or (b= b' and a > a'). Fill in the index at which each of the eight points are being inserted at in the table given. 3. Succinctly give an O(n log n) algorithm for the dominating pairs problem, which is as follows: Given a set of n distinct points in the plane, compute the number of dominating pairs among the n points. (In the example above, the output should thus be 21.) Briefly argue why your algorithm is correct and runs in O(n log n). The problem is designed so that your three answers may all fit into a single page, assuming a normal font-size, normal margins, on a blank page with no header/problem statement.