代做python程序、代写 tree Tpython留学生

日期：2018-05-27 02:10

Exercise 2

We are again interested in lists of pairs of integers. However, this time, we

want to store these pairs into a rooted tree T. More precisely, each node of T

will store a pair of l. This tree T will have the property that for each inner node

k that stores a pair (a,b), the pair (c,d) stored at a node in the subtree of k

satisfies (a,b)≤(c,d). Furthermore, the pairs stored at sibling nodes must be

non-comparable.

We will suppose that the root of the tree is a dummy pair (−1,−1).

You need to provide a unit test for each question in this exercise where code

is required. Each question is evaluated on the correctness of your code and

the thoroughness of your unit tests.

Question 2.1

Define a class that stores the tree T for any given list of pairs. The __init__()

function must take a list as input and build the tree accordingly. An insert()

function must allow the insertion of a pair to an initialised tree. In O(), what is

the running time complexity of the functions you defined?

Question 2.2

In the class you have defined in Question 2.1, can there be multiple trees that

store the same list of pairs? (including after insertions?). Prove your answer.

(write your answer here).

Question 2.3

We now relax the constraint that T must be "exactly" a tree. A child node

which stores a pair (c,d) must now have as a parent all the nodes that have a

pair (a,b) such that (a,b)≤(c,d).

Design a class (it may be based on the previous one) to allow and build this

representation.

Question 2.4

Using the class written in Question 2.3, design and code an algorithm that

traverses all the nodes in that data structure and outputs the stored pairs in

sorted order (as defined in Question 1.2).

Exercise 3

You are given a tree T with an integer value (negative or positive) at each

node. We want to select a subtree of T (with the same root) that maximises

the sum of the values at its nodes. Note that the answer is trivially T if all

nodes have a non-negative value.

Question 3.1

Define a data structure to store T

Question 3.2

Design and code a dynamic programming algorithm that solves this problem.

Question 3.3

Write and run unit tests and performance tests.