2. 6 marks] Max-Tree Value. Consider the problem we will call the mar-tree value problem (MTV):...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
2. 6 marks] Max-Tree Value. Consider the problem we will call the mar-tree value problem (MTV): Given as input the root r of a tree (that is not necessarily binary) in which every node in the tree stores an integer value, return the value stored in a node of maximum value. For example, given the below tree, the algorithm should return value 44. Your algorithm is not responsible for returning the node, just its value. Your algorithm must not modify the tree. Node valse A T 15 " 12 D 36 E 1 F 2 G 6 1 9 M J 10 K 44 L M 10 Design a recursive algorithm that solves the MTV problem. For a node u use e.value to denote the value stored in ; v.isLeaf has value true if node v is a leaf and it has value false otherwise. To access the children of a node v use the following pseudocode: 3 for each childe of v do... You must... a) [3 marks] Write pseudocode (ie. not C++ code) for a recursive algorithm that solves the MTV problem. Please include 1-3 sentences before your pseudocode, in your own words, briefly describing what your algorithm does. To receive full marks, your pseu docode must be clear and has to be correct. b) [3 marks] Compute the worst-case time complexity of your algorithm as a function of the total number n of nodes in the tree. You must explain how you computed the time complexity, and give the time complexity of the algorithm using Big-Theta notation. 2. 6 marks] Max-Tree Value. Consider the problem we will call the mar-tree value problem (MTV): Given as input the root r of a tree (that is not necessarily binary) in which every node in the tree stores an integer value, return the value stored in a node of maximum value. For example, given the below tree, the algorithm should return value 44. Your algorithm is not responsible for returning the node, just its value. Your algorithm must not modify the tree. Node valse A T 15 " 12 D 36 E 1 F 2 G 6 1 9 M J 10 K 44 L M 10 Design a recursive algorithm that solves the MTV problem. For a node u use e.value to denote the value stored in ; v.isLeaf has value true if node v is a leaf and it has value false otherwise. To access the children of a node v use the following pseudocode: 3 for each childe of v do... You must... a) [3 marks] Write pseudocode (ie. not C++ code) for a recursive algorithm that solves the MTV problem. Please include 1-3 sentences before your pseudocode, in your own words, briefly describing what your algorithm does. To receive full marks, your pseu docode must be clear and has to be correct. b) [3 marks] Compute the worst-case time complexity of your algorithm as a function of the total number n of nodes in the tree. You must explain how you computed the time complexity, and give the time complexity of the algorithm using Big-Theta notation.
Expert 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
-
This question was not completed, please fill all answers in box A - L . Thank you! This was all the information provided. Calculate the annual, semiannual, quarterly, and monthly premiums for the...
-
Have a C compiler which is ANSI conforming in all respects except that it has no facility for the definition, declaration or use of standard C structures. Outline a set of routines written in this...
-
(i) Write down the linear program relaxation for the vertex cover problem and solve the linear program. [6 marks] (ii) Based on the solution of the linear program in (b)(i), derive an integer...
-
Read the following statements. In response, state True, False or Uncertain and explain why: (a) Since resources have substitutes, nature imposes particular scarcities, not an inescapable general...
-
A heat engine operating with an environment at 298 K produces 5 kW of power output with a first law efficiency of 50%. It has a second law efficiency of 80% and TL = 310 K. Find all the energy and...
-
Amber Ale use a simple five-step process to prepare its products for shipment. Because of recent increases in demand, the company is setting up an assembly line to do the work. How should the line be...
-
Discuss the potential impact of the Cadbury and COSO report on the audit profession.
-
LaPorta Company and Lott Corporation, two corporations of roughly the same size, are both involved in the manufacture of in-line skates. Each company depreciates its plant assets using the...
-
An earthquake has an intensity of 102'8W/m2. A second earthquake is 1000 times as intense as the first. What is the Richter Scale value of the second earthquake? Select your answer from the options...
-
For each of the following, compute the present value: Note: Do not round intermediate calculations and round your answers to 2 decimal places, e.g., 32.16. Present Value Years Interest Rate Future...
-
PROBLEM 1. Compute the value of the unknown variables (those indicated with the letters A-J). Write your answers on a separate sheet of paper. 2 points each. Lending A B Insitutions Amounts to...
-
a)Discuss whether it would be reasonable to assume positive or negative return spreads will be maintained forever". b) Discuss the advantages and disadvantages of shareholder value analysis (SVA). c)...
-
May I recieve some help with this. It would be very much appreciated. Jeff Dougherty, Chairman of the Board of Mil & Mod Incorporated, wishes to know how a change in capital structure would affect...
-
3. If you were able to earn interest at 3% and you started with $100, how much would you have after 3 years? *
-
B, If Advertising Is Increased To $1733, And The Price Is Kept At $13.86 , How Many Units Does She Need To Sell To Break Even? b, If advertising is increased to $1733, and the price is kept at $13.86...
-
Peanut Company acquired 80 percent of Snoopy Company??soutstanding common stock for $300,000 on January 1, 20X8, when thebook value of Snoopy??s net assets was equal to $375,000. Peanutuses the e 2...
-
1-Stern observed all of the following results EXCEPT _______ in his experiment. A-one of the recombinant phenotypes was associated with an X chromosome of normal length B-the number of car, B+ male...
-
Service firm joint costing Graves Learning Services provides a learning service center to students who want to improve their academic performance. The four service programs currently offered are...
-
Joint product decisions The Pearly Waters Perfume Company manufactures various qualities of perfumes and colognes. One popular line of colognes includes three products that result from a joint...
-
Joint product decision analysis The Maplewood Products Company manufactures three wood treatment products in a joint production process. Each product has certain finish and preservative properties...
Study smarter with the SolutionInn App