Comments on Assignment 1

Code Style

Many students used inconsistent indentation and spacing, which made their programs unnecessarily hard to read.

For example, the inconsistent formatting in this function doesn’t do it any favors:

int sum_ab(int a, int b){
        if (b < a){
                return 0;
        }
        if (a == b) {
                return b;
                }
        else{
                return a + sum_ab(a+1,b);
        }
                }

Coding style matters in real life: poorly formatted code is hard to read and understand, and so often has more errors than well-formatted code.

Better would be this:

int sum_ab(int a, int b){
        if (b < a)
        {
                return 0;
        }
        if (a == b)
        {
                return b;
        }
        else
        {
                return a + sum_ab(a+1,b);
        }
}

Or this:

int sum_ab(int a, int b){
        if (b < a) {
                return 0;
        }
        if (a == b) {
                return b;
        } else {
                return a + sum_ab(a+1,b);
        }
}

Or even this:

int sum_ab(int a, int b){
        if (b < a) return 0;
        if (a == b) return b;
        return a + sum_ab(a + 1, b);
}

Boolean Operators

Don’t use | or & in boolean expressions (e.g. for loops or if- statements). Those operate on bits, and don’t always work the same way as || and && (which is what you should use).

Pre-conditions

Use check_pre or eassert to check that the pre-conditions of functions are satisfied. You are not required to do this, but it is a wise idea as it is a simple way to catch errors.

Some people used if-statements to check pre-conditions, and then returned some sort of error code if they are not satisfied, e.g.:

// Pre: n >= 0
// Post: returns (not prints!) the sum
//       0 + 1 + 2 + ... + n
int sum(int n) {
        if (n < 0) {
                return 0;    // wrong; or at least just as right as
        }                // returning -34893

        // ...
}

While it’s okay to use an if-statement, it is not okay to return an error code unless the post- condition explicitly says that an error code might be returned.

Instead, invalid pre-conditions should call the error() function, e.g.:

// Pre: n >= 0
// Post: returns (not prints!) the sum
//       0 + 1 + 2 + ... + n
int sum(int n) {
        check_pre(n >= 0);   // good: throws an exception if n < 0

        // ...
}

The error() function throws — not returns — an error object out of the function and ends the program.

Efficiency

Many people implemented the partition function correctly but very inefficiently (even ignoring the requirement that recursion be used). We haven’t been talking seriously about performance yet, but you should always keep it in mind and avoid using “expensive” functions whenever possible.

Here’s an example of a needlessly inefficient function (it also has some style issues, but we’ll ignore those here):

bool is_all_pos(const vector<int>& v) {
        if (v.size() == 0) { return true;}
        else if (v.at((v.size()-1)) < 0) {return false;}
        else {
                vector<int> a = v;
                a.pop_back();
               return (is_all_pos(a));}
}

This function makes lots of copies of the vector v, all of them useless. Instead, in a case like this you should use a helper function and begin/end index variables to keep track of the sub-array currently being processed.

Knowledge of C++

Some people are unaware of some simple shortcuts available in C++, and instead use much more arduous methods. For example, here are two different ways to define a vector:

vector<int> v;
v.push_back(1);
v.push_back(-6);
v.push_back(11);
v.push_back(12);

vector<int> w = {1, -6, 11, 12};

The way w is defined is obviously simpler and shorter, and is what you should do. This happens to be a feature of C++11, and some compilers might not support it.

A related issue is printing out a vector. If you are using the std_lib_cmpt225.h header file, then you can do this:

vector<int> v = {6, 8, 7};
vector<string> vs = {"cat", "dog", "mouse"};

cout << v << endl;
cout << vs << endl;

This code prints v and vs in a nice curly-brace style with values separated by commas. There’s no need to use a loop to do this.

Here’s another example of some code that works but is, arguably, not as simple as it could be:

void partition_test_helper( const ::std::vector< int > & src )
{
    ::std::vector< int > v = src;
    partition( v );
    bool isPositiveYet = false;
    ::std::cout << "partitioned vector == { ";
    for ( ::std::vector< int >::const_iterator i = v.begin(); i != v.end(); i++ )
    {
        if ( !isPositiveYet ) isPositiveYet = ( *i > 0 );
        if ( isPositiveYet )
        {
            test( *i > 0 );
        }
        else
        {
            test( *i <= 0 );
        }

        if ( i != v.begin() )
        {
            ::std::cout << ", ";
        }
        ::std::cout << *i;
    }
    ::std::cout << " }\n";
}

There’s no good reason to write ::std::cout instead of just cout. Indeed, it may even be a problem because it prevents the code from using a version of cout specific to CMPT 255 (although no such special cout exists at the moment).

Also, the for-loop uses a iterators, which is a nice way to iterate through a data structure. But the data type of i is big and complex, and can be simplified by using auto:

void partition_test_helper( const vector< int > & src )
{
    vector< int > v = src;
    partition( v );
    bool isPositiveYet = false;
    cout << "partitioned vector == { ";
    for ( auto i = v.begin(); i != v.end(); i++ )
    {
        if ( !isPositiveYet ) isPositiveYet = ( *i > 0 );
        if ( isPositiveYet )
        {
            test( *i > 0 );
        }
        else
        {
            test( *i <= 0 );
        }

        if ( i != v.begin() )
        {
            cout << ", ";
        }
        cout << *i;
    }
    cout << " }\n";
}

The statement auto i = v.begin() declares i to be the data type v.begin() returns. In iterator for-loops like this, auto is almost always the preferred technique because the exact data type of i is usually long and of no value within the loop.

Not Enough Testing

Many people did nowhere near enough testing: often, people would test one case, which is never going to be enough. While determining the exact number of test cases for a function is hard to say in general, you usually want, at least, every line of code to be executed in your function. Any unexecuted lines might have a bug.

Some rules of thumb for testing are:

• Test “boundary values”, e.g. for an int this might be -1, 0, or 1, while for a vector this might be an empty vector or a vector of size 1.
• Test “common cases”, e.g. ordinary cases. Typically only 1 or 2 common cases need to be tested since if one works they probably all do.
• Test “special cases”, e.g. input that you know might cause special problems for your function. You might know these special cases by looking at how the function is implemented, e.g. perhaps it handles odd-sized vectors differently than even-sized vectors.