{"id":2965,"date":"2023-02-20T00:11:11","date_gmt":"2023-02-20T00:11:11","guid":{"rendered":"https:\/\/www.goodacademic.com\/blog\/questions\/adv-design-analy-of-algorithm\/"},"modified":"2023-02-20T00:11:11","modified_gmt":"2023-02-20T00:11:11","slug":"adv-design-analy-of-algorithm","status":"publish","type":"questions","link":"https:\/\/www.goodacademic.com\/blog\/questions\/adv-design-analy-of-algorithm\/","title":{"rendered":"ADV DESIGN & ANALY OF ALGORITHM"},"content":{"rendered":"
\n Learning Goal: <\/b>I’m working on a java discussion question and need an explanation and answer to help me learn.<\/p>\n

In class we have seen implementations of several methods for a scapegoat tree data structure in Java. For this <\/span>
assignment, you will implement four methods as outlined below in Java.
<\/span>0.<\/span>Use the code from class \/ Canvas as a starting point or start yourself from scratch to have a class <\/span>
ScapegoatTree<\/span> with generic key-value nodes.
1.<\/span>Write <\/span>postOrder<\/span> and preOrder<\/span> walk methods which take no input and return a list of tree nodes in the
respective order.
<\/span>2.<\/span>Override the <\/span>toString<\/span> method of the Scapegoat tree class. Use the appropriate form of in-order, pre-order,
or post-order walk to form a string of all current keys which recursively contains parent(children) pairs. Adapt <\/span>
your method from the methods you implemented in Exercise 1. As an example, if a parent has a left and a right
<\/span>child who in turn have left and right grandchildren, your return string would look like
<\/span>parent.key(left.key(lleftgrand.key<\/span>(…), <\/span>lrightgrand.key<\/span>(…)), right<\/span>.key(<\/span>…<\/span>))<\/span>.
<\/span>If exactly one of the children is <\/span>null<\/span>, print a space in its place. If both children are <\/span>null<\/span>, the parent is actually <\/span>
a leaf and no recursion should be executed and no parentheses should be printed.
<\/span>For example, the tree in Figure 1 in the Galperin\/Rivest 1993 paper should yield the string
<\/span>2(1,6(5(4(3, ), ),15(12(9(7,11(10, )),13( ,14)),16( ,17( ,18)))))<\/span>.
<\/span>Hint: It is probably easiest to create the return string while traversing (instead of after traversing) similar to <\/span>
collecting the nodes in the <\/span>inOrder<\/span> method shown in class. That means you would need a mutable string object.
Since Java the String type is immutable, use one of the two mutable Java string types.
<\/span>3.<\/span>Write a public method <\/span>successor<\/span> which finds the successor of a given key by finding the successor node and
returning the key of that node. If a successor does not exist, return the original key. Recall that the successor of <\/span>
a node n<\/span> is either the minimum node in the right subtree of n<\/span> or the first parent of node n<\/span> for which n<\/span> is located
in the left parent sub-tree.
<\/span>4.<\/span>Write a public method <\/span>predecessor<\/span> which finds the predecessor of a given key by finding the predecessor
node and returning the key of that node. If a predecessor does not exist, return the original key. Recall that the <\/span>
predecessor of a node n<\/span> is either the maximum node in the left subtree of n or the first parent of node n for
which <\/span>n<\/span> is located in the right parent sub-tree.
5.<\/span>Test and debug your methods. Provide test runs in form of a main (driver) file in which you create appropriate <\/span>
variables, fill the tree with data from the provided JSON file, and run some cases to show your methods work.
<\/span>Do not forget to upload <\/span>Main.java<\/span> and ScapegoatTree.java<\/span>, as well as a screen shot of test runs. Recall <\/span>
that the Gson<\/span> library needs to be included by going to File\u00e2\u2020\u2019Project Structure\u00e2\u2020\u2019Libraries\u00e2\u2020\u2019+\u00e2\u2020\u2019from Maven,
and then search for com.google.gson.Gson.
<\/span>Each of the problems 1 \u00e2\u20ac\u201c 5 will be graded according to the following rubric for a total of 20 points.
<\/span><\/p>\n

SCORE<\/span> 4<\/span> 3<\/span> 2<\/span> 1<\/span> 0<\/span>
SKILL LEVEL<\/span> Response gives <\/span>
evidence of a <\/span>
complete <\/span>
understanding of <\/span>
the problem; is <\/span>
fully developed; is <\/span>
clearly ——4
communicated.<\/span>
Response gives the <\/span>
evidence of a clear <\/span>
understanding of <\/span>
the problem but <\/span>
contains minor <\/span>
errors or is not <\/span>
fully <\/span>
communicated…….3<\/span>
Response gives <\/span>
evidence of a <\/span>
reasonable <\/span>
approach but <\/span>
indicates gaps in <\/span>
conceptual <\/span>
understanding. <\/span>
Explanations are <\/span>
incomplete, vagu<\/span>e, <\/span>
or muddled……2<\/span>
Response gives <\/span>
some evidence of <\/span>
problem <\/span>
understanding <\/span>
but contains <\/span>
major math or <\/span>
reasoning errors……1<\/span>
No response or <\/span>
response is <\/span>
completely <\/span>
incorrect or <\/span>
irrelevant……0<\/span>
<\/span><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Learning Goal: I’m working on a java discussion question and need an explanation and answer to help me learn. In class we have seen implementations of several methods for a scapegoat tree data structure in Java. For this assignment, you will implement four methods as outlined below in Java. 0.Use the code from class \/ […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"closed","template":"","meta":[],"disciplines":[654],"paper_types":[],"tagged":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/questions\/2965"}],"collection":[{"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/questions"}],"about":[{"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/types\/questions"}],"author":[{"embeddable":true,"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/comments?post=2965"}],"version-history":[{"count":0,"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/questions\/2965\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/media?parent=2965"}],"wp:term":[{"taxonomy":"disciplines","embeddable":true,"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/disciplines?post=2965"},{"taxonomy":"paper_types","embeddable":true,"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/paper_types?post=2965"},{"taxonomy":"tagged","embeddable":true,"href":"https:\/\/www.goodacademic.com\/blog\/wp-json\/wp\/v2\/tagged?post=2965"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}