Tree insertion sort We can sort n objects in O(n log n) unit operations as follows:...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
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. 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. 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.
Expert Answer:
Related Book For
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia
Posted Date:
Students also viewed these algorithms questions
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...
-
The following data pertain to the securities of Linford Company during 2012, the companys first year of operations: a. Purchased 400 shares of Persimmon Corporation stock at $40 per share plus a...
-
Go to Wal-Mart Stores, Inc.'s Web site at www.walmartstores.com. Click on Investors, then select Financial Information; next choose Annual Reports& Proxies; finally, click on the most recent date....
-
How do you think COVID-19 has affected or will affect workplace design? What types of features might employees demand in co-shared work environments?
-
Although the customer loyalty project at Petrie Electronics had gone slowly at first, the past few weeks had been fast-paced and busy, Jim Watanabe, the project manager, thought to himself. He had...
-
During Heaton Companys first two years of operations, the company reported absorption costing net operating income as follows: The companys $18 unit product cost is computed as follows: Forty percent...
-
1. Create a database named "ALBUM" based on the following ERD. (Recall that this is ERD and you need to convert it to relational model and may need to normalize it before implementing in SQL). Make...
-
Assume that you are using attribute sampling to test the controls over revenue recognition of the Packet Corporation, a public company, and will use the results as part of the evidence on which to...
-
2. A coffee shop has the following fixed costs per month: $1,800 rent and utilities and $1,000 for employee wages. The average cup of coffee costs $0.21 in materials. The average price charged for a...
-
what are 5 government policy responses to the financial crisis of 2008 and explain them briefly.
-
0 33 4 0 7 13 10 20 1 now many times will the body of this while loop be executed? int n = 1; while (n
-
Write Python code in MyCalc Class Define basic addition / subtraction / multiplication / division functions These functions should update an internal variable as a running total/value called ans All...
-
A brine solution of salt flows at a constant rate of 4 L/min into a large tank that initially held 100 L of pure water. The solution inside the tank is kept well stirred and flows out of the tank at...
-
If a firm's maximum desired payback period is 3 years, and an investment proposal requires an initial cash outlay of $10.000 and yields the following set of annual cash flows, what is its payback...
-
Consider the following. B = {(5, -2), (-2, 1)}, B' = {(-12, 0), (-4, 4)}, %3D -1 [x] (a) Find the transition matrix from B to B'. |-7/12 -1/4 p-1 = 1/2 1/4 (b) Find the transition matrix from B' to...
-
Which task is performed by a book-keeper? A. Analysing the trading results B. Entering transactions in the ledger C. Preparing year-end financial statements D. Providing information for...
-
Let S = {a, b, c, d, e, f, g} be a collection of objects with benefit-weight values, a: (12, 4), b : (10, 6), c : (8, 5), d: (11, 7), e: (14, 3), f : (7, 1), g : (9, 6). What is an optimal solution...
-
Repeat the previous exercise for the code words, 0, 10, 101, 111. Data From Previous Exercise Fred says that he ran the Huffman coding algorithm for the four characters, A, C, G, and T, and it gave...
-
Prove that there exists a linear program in two variables with exactly one feasible solution.
-
In Example 9.13, the following finite distributed lag model was estimated for Okun's Law using the data file okun5_aus. a. Find the correlogram of the least squares residuals for this model. Is there...
-
Using the data file phillips5_aus, estimate the equation a. Find the first eight lag weights (delay multipliers) of the infinite distributed lag representation that corresponds to this model. What is...
-
Using the data file phillips5_aus, estimate the equation a. Find the first eight lag weights (delay multipliers) of the infinite distributed lag representation that corresponds to this model. What is...
Study smarter with the SolutionInn App