1. [12] Let a1, a2,..., an be a sequence of real numbers, for some n 1....
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
1. [12] Let a1, a2,..., an be a sequence of real numbers, for some n 1. A SUM-BOX is an ADT that stores the sequence and supports the following operations (S is a given SUM-BOX): PARTIAL-SUM(S, m): return a, the partial sum from a to am (1mn). CHANGE(S, i, y): change the value of a; to a real number y. Design a data structure that implements SUM-BOX, using an augmented AVL tree. The worst-case runtime of both PARTIAL-SUM and CHANGE must be in O(logn). Describe your design by answering the following questions. (a) What is the key of each node in the AVL tree? What other attributes are stored in each node? (b) Write the pseudo-code of your PARTIAL-SUM operation, and explain why your code works correctly and why its worst-case running time is O(logn). Let S.root denote the root node of the AVL tree. (c) Describe in clear and concise English how your CHANGE operation works, and explain why it runs in O(logn) time while maintaining the attributes stored in the nodes of the AVL tree. 1. [12] Let a1, a2,..., an be a sequence of real numbers, for some n 1. A SUM-BOX is an ADT that stores the sequence and supports the following operations (S is a given SUM-BOX): PARTIAL-SUM(S, m): return a, the partial sum from a to am (1mn). CHANGE(S, i, y): change the value of a; to a real number y. Design a data structure that implements SUM-BOX, using an augmented AVL tree. The worst-case runtime of both PARTIAL-SUM and CHANGE must be in O(logn). Describe your design by answering the following questions. (a) What is the key of each node in the AVL tree? What other attributes are stored in each node? (b) Write the pseudo-code of your PARTIAL-SUM operation, and explain why your code works correctly and why its worst-case running time is O(logn). Let S.root denote the root node of the AVL tree. (c) Describe in clear and concise English how your CHANGE operation works, and explain why it runs in O(logn) time while maintaining the attributes stored in the nodes of the AVL tree.
Expert Answer:
Answer rating: 100% (QA)
a The key of each node in the AVL tree will be the index of the element in the sequence Each node wi... View the full answer
Related Book For
Posted Date:
Students also viewed these programming questions
-
"internet radios" for streaming audio, and personal video recorders and players. Describe design and evaluation processes that could be used by a start-up company to improve the usability of such...
-
Design a Java class that represents a cache with a fixed size. It should support operations like add, retrieve, and remove, and it should evict the least recently used item when it reaches capacity.
-
The two key principles that form the foundation for an ethical sales presentation are OA) the approach and the close B) setting up the appointment and completing the application C) uncovering needs...
-
Fried dough is a popular North American food associated with outdoor food stands at carnivals, amusement parks, fairs, and festivals, etc. Usually dusted with powdered sugar and drenched in oil, it...
-
1. How has Cirque du Soleil leadership been able to create a new market space in a traditional industry? Is setting a direction, designing the organization, nurturing a culture sufficient to create a...
-
Redesign the fractionator of Example 6.8 for a reflux ratio that is twice the minimum. Determine the diameter of the tower, the height of packing in the stripping and rectifying sections, and the...
-
Faith Evans Corporation is a regional company which is an SEC registrant. The corporations securities are thinly traded on NASDAQ (National Association of Securities Dealers Quotes). Faith Evans...
-
1. The rate at which a bean plant grows is given by a differentiable function R(t). measured in centimeters per day, where 0 st s 30. A graph of the function R is shown below along with a table of...
-
Write a report to research correctional systems to determine correctional best practices for particular program areas. To synthesize program elements and structures to provide the basis for a program...
-
You are given the following quotation USD/CAN CAN/MYR GBP/BND MYR/BND USD/SGD Buying Selling 1.0010 1.0050 2.9960 2.9995 2.2420 2.3655 0.3450 1.2030 0.3650 1.2060 Compute the following. i. Cross-rate...
-
A meniscus lens with a refractive index of 1.490 has a center thickness of 4.5mm, a front radius of curvature of +44.55 mm, and back radius of curvature of +81.67 mm. Find the two surface powers and...
-
Module 05 Content You will expand the outline you wrote in Module 3 into a complete paper.There is no set length for the paper, though the average length is four or five pages. Citations are not...
-
Museum owns two of the three gemstones that were once lodged in the "Triforce Crown," a famous ancient relic, but not the crown itself, which has been lost for centuries. The third gemstone ("the...
-
1. Make a list of jobs that you think require really good problem solving skills. 2. What are some of the problems college students have to solve? 3. What are the steps you take to solve problems? 4....
-
A loan of $17,200 at 9% compounded monthly is to be paid off by equal payments to be made at the end of every month for three years. What is the size of the monthly payment?
-
Refer to the information from Exercise 22-19. Use the information to determine the (1) Weighted average contribution margin , (2) Break-even point in units, and (3) Number of units of each product...
-
Let H V Rn, with H convex and V open, and suppose that : V Rn is C1. a) Show that if E is a closed subset of H and then h(x)/||h|| 0 uniformly on E, as h 0. b) Show that if R is a closed...
-
Suppose that H = [a, b] Ã [c, d] is a rectangle, that f: H R is continuous, and that g: [a, b] R is integrable. Prove that is uniformly continuous on [c, d]. e b F(y) # 1 g(x)f(x,y)dx
-
The distance from a point x0 = (x0, y0, z0) to a plane II in R3 is defined to be where v := (x0 - x1, y0 - y1, z0 - z1) for some (x1, y1, z1) II, and v is orthogonal to II (i.e., parallel to its...
-
The financial records of Dunbar Inc. were destroyed by fire at the end of 2015. Fortunately, the controller had kept the following statistical data related to the income statement. 1. The beginning...
-
Maher Inc. reported income before income tax during 2015 of 790,000. Additional transactions occurring in 2015 but not considered in the 790,000 are as follows. 1. The corporation experienced an...
-
Presented below is the trial balance of Thompson Corporation at December 31, 2015. Instructions Prepare an income statement and a retained earnings statement. Assume that the only changes in retained...
Study smarter with the SolutionInn App