EEE computing

Assignment 2 (Spring 2021)

This assignment deals with the representation of boolean functions (in the sense of logic functions, not of C++ functions) using linked data structures. Let's begin with an example.

Consider the logic and boolean function, with two parameters x1 and x2 and the following truth table:

It can be represented in a tree-like form as follows (a left branch represents assigning a 0 to that parameter, a right branch assigning a 1):

In C++ this can be implemented as a linked data structure whose nodes are defined by a structured data type. Complete the following code:

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

// "x1", "x2"... "xn" 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 other functions to be used in the two functions below

// if you want you can also define and use other

// structured data types or classes including member data and member functions

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

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

// implement this function (see explanation further down)

}

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

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

// implement this function (see explanation further down)

}

// add a main for you to test your program

// but the content of the main won't be considered for the assessment

build_bt

This function builds a (tree-like) linked data structure corresponding to the (logic) boolean function provided in input and returns a pointer to the first node of the linked data structure. The input contains only the rows of the truth table with a value of 1 for the boolean function.

For example for the and boolean function we would have:

int main(){

std::vector<std::string> fvalues;

std::string row;

row = "11";

fvalues.push_back(row);

BNode* bt;

bt = build_bt(fvalues);

// here we would normally include a function call to deallocate

// the linked data structure pointed by bt

// but it's omitted to avoid confusion as you are not required

// to submit the implementation of said deallocation function

// and the main is not considered during the assessment

// (the same applies to the other examples of main below)

}

For the or boolean function we could have:

int main(){

std::vector<std::string> fvalues;

std::string row;

row = "01";

fvalues.push_back(row);

row = "10";

fvalues.push_back(row);

row = "11";

fvalues.push_back(row);

BNode* bt;

bt = build_bt(fvalues);

}

However the function must work whatever the order of the lines so for the or boolean function we could also equivalently have for example:

int main(){

std::vector<std::string> fvalues;

std::string row;

row = "11";

fvalues.push_back(row);

row = "01";

fvalues.push_back(row);

row = "10";

fvalues.push_back(row);

BNode* bt;

bt = build_bt(fvalues);

}

We consider boolean functions with any number (greater than 0) of parameters. We could have for instance a function with six parameters whose value is always 0 except for the following lines of the truth table:

In which case we could have for example:

int main(){

std::vector<std::string> fvalues;

std::string row;

row = "000010";

fvalues.push_back(row);

row = "010010";

fvalues.push_back(row);

row = "110011";

fvalues.push_back(row);

BNode* bt;

bt = build_bt(fvalues);

}

Note that the order of the values within each string is important, for example if we have “000010” then the parameter with value 1 in that string is expressed unambiguously as corresponding to x5.

eval_bt

This function takes in input a pointer to the first node of a linked data structure representing a boolean function and a string representing the values for the parameters of the boolean function and returns the value of the boolean function for that configuration of values.

For example:

int main(){

std::vector<std::string> fvalues;

std::string row;

row = "000010";

fvalues.push_back(row);

row = "010010";

fvalues.push_back(row);

row = "110011";

fvalues.push_back(row);

BNode* bt = build_bt(fvalues);

std::cout << eval_bt(bt, "000010") << std::endl;

// should print "1"

std::cout << eval_bt(bt, "000001") << std::endl;

// should print "0"

}

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.

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).

Assessment criteria

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

● All the requirements and guidelines must be respected.

● 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.

Within the 70%-100% range the criteria are:

● 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).

Q&A

I am not sure how to do something and it's not in the notes.

Yes, some aspects of this assignment require you to do some autonomous study using for example resources such as the C++ documentation.

The following program also shows an example of some useful operations on std::string:

#include <iostream>

#include <string>

bool contains_letter(std::string letter, std::string word){

std::string word_i;

// we can use member function size on std::string as we would do for std::vector

for(int i = 0; i < word.size(); i++){

// we can index an std::string character by character

// using [] as we would do for std::vector

// but the return is of type char, not of type std::string

// and we can't compare a char and an std::string directly

// however if we add the char to an empty std::string

// using push_back (once again as we would do for std::vector)

// we obtain an std::string containing the character

word_i = "";

word_i.push_back(word[i]);

// now we can compare the two std::string

if(letter == word_i){

return true;

}

}

return false;

}

int main(){

std::string word, letter;

std::cout << "please enter a word" << std::endl;

std::cin >> word;

std::cout << "please enter a letter" << std::endl;

std::cin >> letter;

if(contains_letter(letter, word)){

std::cout << letter << " is contained in " << word << std::endl;

}

else{

std::cout << letter << " is not contained in " << word << std::endl;

}

}

Can I assume that the functions will always be tested with meaningful and consistent input?

Yes.

Can I make the data structure start from a node other than x1? Or rearrange the order, e.g. have nodes other than x2 at the level below x1? Or reduce the number of allocated nodes for example by having that nodes can have several parent nodes or that left and right point to the same node etc?

No, you must keep everything as shown in the requirements also because the automated testing will not work if you make changes of this kind.

Consider again the figure shown above:

each node in the figure must be a distinct node allocated at a different address in memory, even though several of them will have the same content for the val member data, for example all the leaf nodes with value 0.

Should I add comments?

Feel free to add some 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.

When will the grades be available?

B y the end of the first week of Summer term (Friday 30th April) grades and feedback for most submissions (those not presenting particular issues) will be available on Blackboard (I will send a notification email).

Can you or a TA help me with the assignment?

No because it's assessed. We can however help you with other exercises on the topics involved in the assignment.

I have another question.

Sure, you can send me an email but:

1) First please reread this page and double check that the answer isn't already here or elsewhere on this website or on Blackboard.

2) Make sure you send your email by Tuesday 23rd March as I am unlikely to answer emails received after that.