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