Let A be an integer array and n is the number of elements in the array....
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Let A be an integer array and n is the number of elements in the array. Letj, k and m are arbitrary indexes of array A. Let h be the height of a tree. LEFT(i) means index of left child of node at i. RIGHT (i) means index of right child of node at i. Assume a comparison fails when an index is not set within array bounds or when not set at all. (a) Given an unsorted integer array below and its initial tree representation (The numbers above nodes represent array indexes), Apply the following two procedures, BUILD-TREE and FIX-TREE, to this initial tree to produce a final tree. Show your work by showing intermediate stages of the tree building after each iteration. (15 points) A 14 1 4 2 2 3 4 5 6 7 8 9 10 1 3 2 16 9 10 14 8 7 8 1 10 7 5 16 I 4 9 3 7 10 BUILD-TREE (A, n) for i = FLOOR[n/2] downto 1 do FIX-TREE (A, i, n) FIX-TREE(A, i, n) j=LEFT(i) k = RIGHT(i) if j n and A[j] > A[i] then m = j else m = i if k n and A[k] > A[m] then m = k if m != i then SWAP (A[i], A[m]) FIX-TREE(A, m, n) (b) What is the time comlexity of BUILD-TREE method? (2 points) (c) What is the time comlexity of FIX-TREE method? (3 points) Let A be an integer array and n is the number of elements in the array. Letj, k and m are arbitrary indexes of array A. Let h be the height of a tree. LEFT(i) means index of left child of node at i. RIGHT (i) means index of right child of node at i. Assume a comparison fails when an index is not set within array bounds or when not set at all. (a) Given an unsorted integer array below and its initial tree representation (The numbers above nodes represent array indexes), Apply the following two procedures, BUILD-TREE and FIX-TREE, to this initial tree to produce a final tree. Show your work by showing intermediate stages of the tree building after each iteration. (15 points) A 14 1 4 2 2 3 4 5 6 7 8 9 10 1 3 2 16 9 10 14 8 7 8 1 10 7 5 16 I 4 9 3 7 10 BUILD-TREE (A, n) for i = FLOOR[n/2] downto 1 do FIX-TREE (A, i, n) FIX-TREE(A, i, n) j=LEFT(i) k = RIGHT(i) if j n and A[j] > A[i] then m = j else m = i if k n and A[k] > A[m] then m = k if m != i then SWAP (A[i], A[m]) FIX-TREE(A, m, n) (b) What is the time comlexity of BUILD-TREE method? (2 points) (c) What is the time comlexity of FIX-TREE method? (3 points)
Expert Answer:
Answer rating: 100% (QA)
a Initial tree representation 1 2 3 4 5 16 6 9 7 10 8 14 After apply... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
Under which article does legitimate national law overrule conflicting state laws?
-
How can a company optimize its supply chain operations to minimize costs while ensuring efficient delivery and quality control? Discuss the various strategies, such as lean manufacturing, inventory...
-
2. Mary, who is single, and lives in south Florida, suffered damage to her house and car during a flood in a federally declared disaster area. Her house, in which she had a basis of $150,000, had a...
-
The management of Mecca Copy, a photocopying centre located on University Avenue, has compiled the following data to use in preparing its budgeted balance sheet for next year: Ending Balances...
-
A process with no beginning work in process, completed and transferred out 28,000 units during a period and had 12,000 units in the ending work in process that were 50% complete. How much is...
-
The makeup of various groups within the U.S. population may reshape the electorate in ways that could change political representation and policies. By using U.S. Department of Labor data from 1980...
-
Develop contactor designs that combine advantages of cocurrent, crossflow, and countercurrent cascades.
-
The Kool King Company has followed a policy of no layoffs for most of the manufactures tile, even though the demand for its air conditioners is highly seasonal. Management wants to evaluate the cost...
-
Yogi Berra When a waitress asked Yogi Berra, Baseball Hall of Fame catcher for the New York Yankees, whether he wanted his pizza cut into four pieces or eight, Yogi replied: "Better make it four. I...
-
You work at DeliWine, a US wine retailer. DeliWine sources one of their best selling wines, JeanRose, from a Dutch wine distributor. The cost of placing an order is $ 513 and the annual holding cost...
-
Creating an ER diagram Instructions In this exercise you will create an ER diagram according to the instructions below: Use the application of your choice to create the ER diagram.As an...
-
Explain how you can use QuickBooks Accountant to modify any report.
-
Which menus are used to create budget reports in QuickBooks Accountant?
-
Describe how you use the calculator feature that is built into QuickBooks Accountant.
-
What different graphs are available in QuickBooks Accountant?
-
When you create a balance sheet, what is the result of clicking the Collapse button?
-
Roger's wife, the primary wage earner for their household, passed away three months ago, leaving Roger alone to care for three small kids. After weeks of looking, Roger just got a new job that he...
-
Determine two different Hamilton circuits in each of the following graphs. A B F G
-
The join operation takes two dynamic sets S 1 and S 2 and an element x such that for any x 1 S 1 and x 2 S 2 , we have x 1 .key x.key x 2 .key. It returns a set S = S 1 {x} S 2 . In this...
-
Suppose that we were to implement B-TREE-SEARCH to use binary search rather than linear search within each node. Show that this change makes the CPU time required O(lg n), independently of how t...
-
Show that for any integer n ? 0, n k = n2"-1 k=0
-
You are an internal auditor for the Military Industrial Company. You are presently preparing test transactions for the companys weekly payroll processing pro gram. Each input record to this program...
-
The program computes federal withholding tax for each employee by multiplying gross pay times a tax rate determined from Table 9-9. The program next computes state withholding tax for each employee...
-
An auditor is conducting an examination of the financial statements of a wholesale cosmetics distributor with an inventory consisting of thousands of individual items. The distributor keeps its...
Study smarter with the SolutionInn App