辅导EEE computing程序、讲解C++设计编程 讲解SPSS|辅导R语言程序

日期：2021-03-20 09:02

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:
x1 x2 x1 and x2
0 0 0
0 1 0
1 0 0
1 1 1
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
#include
#include
// 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
2021/3/17 progeng:a2sp21 [EEE computing]
https://intranet.ee.ic.ac.uk/m.cattafi/scripts/dw/doku.php?id=progeng:a2sp21 2/6
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& 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 returns a pointer to the first node of the linked data structure representing the boolean function. 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 fvalues;
std::string row;
row = "11";
fvalues.push_back(row);
BNode* bt;
bt = build_bt(fvalues);
}
For the or boolean function we could have:
int main(){
std::vector 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);
2021/3/17 progeng:a2sp21 [EEE computing]
https://intranet.ee.ic.ac.uk/m.cattafi/scripts/dw/doku.php?id=progeng:a2sp21 3/6
}
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 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:
x1 x2 x3 x4 x5 x6 f(x1, x2, x3, x4, x5, x6)
0 0 0 0 1 0 1
0 1 0 0 1 0 1
1 1 0 0 1 1 1
In which case we could have for example:
int main(){
std::vector 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 fvalues;
2021/3/17 progeng:a2sp21 [EEE computing]
https://intranet.ee.ic.ac.uk/m.cattafi/scripts/dw/doku.php?id=progeng:a2sp21 4/6
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
2021/3/17 progeng:a2sp21 [EEE computing]
https://intranet.ee.ic.ac.uk/m.cattafi/scripts/dw/doku.php?id=progeng:a2sp21 5/6
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
#include
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 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:
2021/3/17 progeng:a2sp21 [EEE computing]
https://intranet.ee.ic.ac.uk/m.cattafi/scripts/dw/doku.php?id=progeng:a2sp21 6/6
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?
By 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.
progeng/a2sp21.txt · Last modified: 2021 by mc