EEE computing

Assignment 3 (Summer term 2021)

In the second assignment we considered the representation of logic boolean functions using linked data structures structured as trees. In that case we wanted to always generate a full tree.

In this assignment we deal with tree representations that keep the full information and respect a set of requirements but contain fewer nodes than the full tree.

Let's consider again the logic and boolean function, with two variables x1 and x2 and the following truth table:

We can represent it in this “full” form which was required in the previous assignment (a left branch represents assigning a 0 to that logic variable, a right branch assigning a 1):

For this assignment the idea is to represent it instead with fewer nodes, for example as follows (also in this case a left branch represents assigning a 0 to that logic variable, a right branch assigning a 1):

For this assignment this is also a valid and equivalent representation for this boolean function:

Consider also the following example:

This function can be represented as follows:

In this assignment we aim to represent it with fewer nodes, for example as follows:

Or, with even fewer nodes (therefore more effectively for our aims) as follows:

Deliverables

There are two deliverables for this assignment: the code and a report.

Code

You are given the following code to complete (see also the instructions provided in the comments) and submit on Blackboard using the “Code submission for assignment 3” submission area in the “Submission for assignment 3 (Summer term 2021)” folder.

bt.cpp

#include <iostream>

#include <vector>

#include <string>

// you can include other headers

// you need for your code

// you can use only headers from the C++ standard library

// you can use any headers from the C++ standard library

// except for the algorithm header

// do not use "using namespace std;"

// do not alter this structured data type definition

struct BNode{

std::string val;

// this will contain

// "xn" (e.g. x3 or x1 etc) in non-leaf nodes

// "0" or "1" in leaf nodes

BNode* left;

// this will conventionally represent the 0 branch

BNode* right;

// this will conventionally represent the 1 branch

// (as usual leaf nodes will have both left and right pointing to NULL)

};

// you can define here other functions to use in the code below

// you can also define here other

// structured data types or classes

// (including member data and member functions)

// to use in the code below

// do not alter the following line that begins the function build_bt

BNode* build_bt(const std::vector<std::string>& fvalues){

// complete this function

}

// do not alter the following function

// this function converts e.g. std::string "x3" to int 2

int label_to_idx(const std::string& label){

std::string out;

for(int i = 1; i < label.size(); i++){

out.push_back(label[i]);

}

return std::stoi(out) - 1;

}

// do not alter the following function

std::string eval_bt(BNode* bt, const std::string& input){

if( (bt->left == NULL) && (bt->right == NULL) ){

return bt->val;

}

else{

int idx = label_to_idx(bt->val);

std::string input_idx;

input_idx.push_back(input[idx]);

if(input_idx == "0"){

return eval_bt(bt->left, input);

}

else{

return eval_bt(bt->right, input);

}

}

}

// do not alter the following function

int n_nodes_bt(BNode* t){

if(t == NULL){

return 0;

}

else{

return 1 + n_nodes_bt(t->left) + n_nodes_bt(t->right);

}

}

class BoolTree{

public:

BoolTree(const std::vector<std::string>& fvalues){

t = build_bt(fvalues);

}

std::string eval(const std::string& s){

return eval_bt(t, s);

}

int n_nodes(){

return n_nodes_bt(t);

}

~BoolTree(){

// complete this function

// (do not alter in any other way class BoolTree)

// keep in mind that you can include in this function

// calls to functions defined outside class BoolTree

// (as done in the member functions above)

// and that you can define other functions

// above and outside this class

}

private:

BNode* t;

};

// the main provided below must work correctly

// with your implementation for the code above

// however you can change it as you wish for your own testing

// and your changes won't be considered for the assessment

// (in your submission you can also have an empty main or no main at all)

int main(){

std::vector<std::string> fv;

std::string row;

row = "11";

fv.push_back(row);

BoolTree ft1(fv);

// as in the second assignment we give as input only the rows

// of the truth table whose value is 1

// (this is an example with the boolean "and" function)

fv.clear();

row = "010";

fv.push_back(row);

row = "011";

fv.push_back(row);

row = "110";

fv.push_back(row);

row = "111";

fv.push_back(row);

BoolTree ft2(fv);

// this corresponds to the f(x1, x2, x3) example shown above

std::cout << ft1.n_nodes() << std::endl;

// we expect this to print 5

std::cout << ft2.n_nodes() << std::endl;

// if the algorithm is such that it builds the smallest possible corresponding tree

// for the boolean function we are considering

// then this will print 3 (see tree diagram in the example above)

std::cout << ft1.eval("01") << std::endl;

// this should print "0"

std::cout << ft1.eval("11") << std::endl;

// this should print "1"

std::cout << ft2.eval("001") << std::endl;

// this should print "0"

std::cout << ft2.eval("110") << std::endl;

// this should print "1"

}

In this assignment function build_bt (which is called by the constructor of class BoolTree) builds the tree corresponding to the boolean function while also aiming to do so with fewer nodes than in the version we considered in the second assignment.

The structure of the tree built by function build_bt must respect the requirements.

In particular the resulting tree must work correctly (which includes not having undefined behaviour) with the implementation of eval_bt and of n_nodes_bt as provided, otherwise your program will be considered not correct.

Consider also that 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 a correct structure:

Report

The report should include two sections: one about the algorithm you implemented and one about testing and evaluation. More details are provided below. Submit the report using the “Report submission for assignment 3” Turnitin submission area in the “Submission for assignment 3 (Summer term 2021)” folder.

Algorithm

One to three pages explaining the algorithm you implemented (your algorithm can also be the integration of several different (sub)algorithms of course). Include at least one worked example showing step by step how the algorithm you implemented works on a specific boolean function. Keep the focus on the algorithm, not on which variables you declared etc (this would be about the implementation in code, not the algorithm). Including pictures and diagrams (you can also draw them by hand) is probably a good idea.

Testing and evaluation

One to two pages about your testing and evaluation of your program. On which boolean functions did you test your program? How many variables do they have? How many nodes does your program manage to reduce? Can you see any patterns? Does your final version perform better than your initial one, and why? Including tables and graphs is probably a good idea.

Guidelines

Please note that there are important guidelines also in the comments in the source code above. None of the functions, except for the main, should contain user or file input or output (std::ifstream, std::cin, std::cout, etc) in their implementation. In other words, std::ifstream, std::cin, std::cout, etc are only allowed in the main. If you add any of these to other functions for debugging purposes you must remove them before submitting.

All the variables should 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 should be controlled/terminated either by the loop condition or by return. Statements such as break, continue, goto are not allowed anywhere in the program.

Do not use the switch statement.

Do not use the static keyword.

Our reference C++ compiler is the one on repl. To make sure that your program respects the standard, periodically check that your code runs and works as expected also on repl (but do not leave your code for the assignment on repl for longer than it takes to test that it works).

Input

You can assume that the functions will always be tested with meaningful and consistent input and you don't have to check for consistent input.

Comments

Feel free to add some comments if you think they would be useful for yourself to understand your own code or to explain some aspects of your program, but it is more important that your code is clear and readable on its own, minimising the need for comments.

Do not add too many comments: that will only make us waste time by having to remove them before we check your submission.

The code draft has already some comments containing instructions, etc. You can leave them in your submission or remove them, that's up to you.

Assessment

Assessment criteria

In order to be awarded a mark in the the 55%-100% range, a submission must fulfill all of these conditions:

● All the requirements and guidelines must be respected.

● The program must perform the task for this assignment. It doesn't have to always manage to represent the tree with fewer nodes than the full tree and it doesn't have to always achieve the minimum reduction. But it has to achieve at least some reduction in at least some general cases (otherwise it would be the same as the second assignment).

● We don't assess on how fast the program is, but the tree must be built by the function within a reasonable time because the testing can't wait indefinitely. We will use a timeout of several seconds and the instances will not be too large.

● The code must be entirely correct. For example (this is not an exhaustive list):

● If one or more of the automated tests are not passed, the code is not correct.

● If there are occurrences of crashes, infinite loops, or infinite recursion, the code is not correct.

● If there are undefined behaviour instructions in the code, then it is not correct (regardless of whether or not it is noticeable when the program is run).

● The code must be generally well indented and formatted and readable, with reasonably meaningful names for the variables.

If the criteria above are respected then a 55% baseline is acquired and the following criteria are also considered:

10% based on the following:

● The more readable the code, the better.

● Good functional decomposition should be applied, also in order to avoid code duplication.

● The code doesn't need to be optimised for efficiency, but wastefulness should be avoided, as in the examples in the notes. Think of the prime number example, in which the loop terminates as soon as the first factor is found (instead of going on to try other potential factors) or as soon as the square root of the number is reached (instead of trying all the numbers up to the input).

15% based on the extent of the reduction in the number of nodes achieved by your program tested on several different instances. This will be evaluated by comparison to the other submissions. The number of nodes will be counted using the implementation of n_nodes_bt as provided in the code above.

20% based on the report: content, clarity, overall quality (make sure you proofread it before the submission). A two-pages concise meaningful clear report is much better than a long one with unclear explanations and little meaningful information.

Grades and feedback

By Monday 14 June grades and feedback for most submissions (those not presenting particular issues) will be available on Blackboard (I will send a notification email).

Plagiarism and collusion

I remind you that this is an individual assignment. When you are given an individual assignment, you are expected to submit only your own work, as during an exam. Thus, you are expected not to submit work based on someone else's, not to show your work to others and not to work in collaboration with others.

Asking a question or discussing this assignment

For anything related to this assignment please submit this form (do not send an email) by Monday 24 May 11:30am (UK time):

https://forms.office.com/Pages/ResponsePage.aspx?id=B3WJK4zudUWDC0-CZ8PTB-75UF3OdNBPqXB4H5AaYd5UM1g2UTdLRjROUE5OV0lUVkw0RENIMDJYTi4u

[https://forms.office.com/Pages/ResponsePage.aspx?id=B3WJK4zudUWDC0-CZ8PTB-75UF3OdNBPqXB4H5AaYd5UM1g2UTdLRjROUE5OV0lUVkw0RENIMDJYTi4u]

Although I cannot help you with the assignment because it's assessed, I can still help you with other exercises on the topics involved in the assignment and if you feel stuck I can give you some general guidance on getting unstuck.

If you have a question about the requirements I encourage you to first look for the answer in the page again and make sure you have read everything before you submit the form.