program代写、Python/Java程序代写

日期：2023-05-30 09:25

EEE computing

Assignment 3 (Summer 2023)

Please read the whole page word by word from top to bottom at least once. Do not just skim through.

Before you ask a question please check again whether the answer can already be found here and give

yourself some time to think.

Context

In this assignment we are going to apply what we have seen in the second assignment to a task from data mining and

machine learning.

Let's begin with an example. Imagine someone who goes kayaking on days with different conditions and keeps a record

such as the following one, in which a certain configuration of conditions (temperature, rain, wind) is labeled with an

assessment of the quality of the experience:

temperature rain wind quality

high yes light acceptable

low yes light acceptable

low no moderate good

high yes strong poor

high yes moderate acceptable

high no moderate good

low yes strong poor

high no light good

low yes moderate poor

high no strong poor

The rows are not in any particular order and not all the possible combinations are present.

A first example of tree representation

We could for example represent this information as a tree as follows:

We consider the implementation of such trees using a variation of the implementation we have seen in the second

assignment.

As you can see, in this assignment the edges are labeled. So the EdgeNode structured data type will also have a val field to

label the edge:

struct EdgeNode{

tree_t val;

TreeNode* subtree;

EdgeNode* next;

};

You can also see that in this assignment there can be repetitions in the tree.

The tree above with a different order for the edges

In this assignment the order of the edges doesn't matter, therefore the following tree would be considered equivalent to the

previous one:

temperature

low high

rain

rain

yes no no yes

wind wind

good wind

light

acceptable

moderate strong

poorpoor

light

good

moderate strong

goodpoor

light

acceptable

moderate strong

acceptable poor

A tree representation with fewer nodes

The following tree represents the same information in fewer nodes, therefore it is more effective for our purposes:

Not a tree

The nodes of a tree cannot have several parents (otherwise it's not a tree, it's a different data structure) therefore for

example this would not be correct:

temperature

Ow high

rain rain

yes no yes no

wind good

wind wind

light moderate strong light strong

acceptable poorpoor

light

good

moderate

strongmoderate

poor good acceptableacceptable poor

no

good

lgi h t

rain

yes

acceptable

wind

moderate strong

rain poor

good

yes

temperature

low high

poor acceptable

Implementation

Write a class called A3Tree that can be used for the purpose illustrated by the example above. The following is an example

of a main with testing for the example above (header inclusions have been omitted), use this example to infer what member

functions need to be included in the class:

int main(){

// direct initialisation of a vector

// in this case it's a vector containing vectors

// each of which contains words (std::string)

std::vector<std::vector<std::string>> input

{

{"temperature", "rain", "wind", "quality"},

{"high", "yes", "light", "acceptable"},

{"low", "yes", "light", "acceptable"},

{"low", "no", "moderate", "good"},

{"high", "yes", "strong", "poor"},

{"high", "yes", "moderate", "acceptable"},

{"high", "no", "moderate", "good"},

{"low", "yes", "strong", "poor"},

{"high", "no", "light", "good"},

{"low", "yes", "moderate", "poor"},

{"high", "no", "strong", "poor"}

};

A3Tree t(input);

// direct initialisation of a vector:

std::vector<std::string> q{"low", "yes", "strong"};

std::cout << t.query(q) << std::endl;

// this should print: poor

// assigning new content overwriting the previous content:

q = {"high", "yes", "moderate"};

std::cout << t.query(q) << std::endl;

// this should print: acceptable

std::cout << t.node_count() << std::endl;

// this depends on the actual tree generated,

// if we consider the tree in the example which

// has wind in the root node this should print: 10

std::cout << t.leaf_node_count() << std::endl;

// this depends on the actual tree generated,

// if we consider the tree in the example which

// has wind in the root node this should print: 6

}

As mentioned above, the implementation must be based on a variation of what we have seen in the second assignment, so

you will need to include (and meaningfully use) the following (include it as given, do not alter it):

struct TreeNode;

struct EdgeNode;

typedef std::string tree_t;

struct EdgeNode{

tree_t val;

TreeNode* subtree;

EdgeNode* next;

};

struct TreeNode{

tree_t val;

EdgeNode* subtree_l;

};

Within the A3Tree class definition it will therefore look like this:

class A3Tree{

// there will be other code here

private:

TreeNode* t;

// member data pointing to the root of the tree

// do not change the name or anything else regarding

// this member data declaration

};

You can define and use all the additional functions, member data, member functions, structured data types, classes you

need.

Write some comments at the beginning of each function or member function to explain what it does. Do not comment

code line by line. Remember that it is important that your code is clear and readable (minimising the need for comments).

You can include any headers from the standard library except for the algorithm header.

Submit a main that includes evidence of your testing and include some comments on the testing. For our testing we will also

replace your main with our own main.

Your implementation should work in principle on an input with any number of columns and in which any number of

distinct values may appear in each column. You can assume that the names of the columns and the values have no spaces.

For example:

int main(){

std::vector<std::vector<std::string>> input1

{

{"temperature", "rain", "wind", "quality"},

{"high", "yes", "light", "acceptable"},

{"low", "yes", "light", "acceptable"},

{"low", "no", "moderate", "good"},

{"high", "yes", "strong", "poor"},

{"high", "yes", "moderate", "acceptable"},

{"high", "no", "moderate", "good"},

{"low", "yes", "strong", "poor"},

{"high", "no", "light", "good"},

{"low", "yes", "moderate", "poor"},

{"high", "no", "strong", "poor"}

};

std::vector<std::vector<std::string>> input2

{

{"Feature_3", "feature2", "feature", "feature0", "not_a_feature"},

{"a13480", "10", "a13480", "a", "1"},

{"B_34203", "9", "1343432", "a", "a2"},

{"a13480", "8", "57657", "a", "3"},

{"B_34203", "B_34203", "4523", "a", "2"},

{"B_34203", "6", "4523", "a", "some_value"},

{"a13480", "5", "4523", "a", "1"}

};

A3Tree t1(input1);

A3Tree t2(input2);

std::vector<std::string> q;

q = {"high", "yes", "moderate"};

std::cout << t1.query(q) << std::endl;

// this should print: acceptable

q = {"B_34203", "9", "1343432", "a"};

std::cout << t2.query(q) << std::endl;

// this should print: a2

}

Destructor, copy constructor, assignment operator

Remember to include a suitable destructor.

The copy constructor and assignment operator would be needed for correct design but they are outside the scope of

this assignment, do not include them.

Guidelines

You can assume that the implementation will always be tested with valid, meaningful and consistent input. The vector (of

vectors of string) passed in input to the constructor of class A3Tree will be consistent and with no repetitions (in the sense

of no repetitions of rows) and it will not be empty. Member function query will not be tested giving in input an inconsistent

or empty vector or a vector representing a row that did not appear in the input to the constructor.

Outside of the main do not add any user input or output or file input or output.

All the variables must be declared in the scope of a function (either the main or some other one). In other words, global

variables are not allowed.

All the loops must be controlled/terminated either by the loop condition or by return. Statements such as break,

continue, goto are not allowed anywhere in the code.