Assignment 0

“Assignment 0” is not a real assignment; you don’t get any points for completing it (because I’m going to give you the complete solution in class), which also means you don’t lose any points for not doing it. Still, it may be helpful for you to do it, as it introduces a lot of things that will be common to all the future assignments.

Starting out

Every assignment must be “submitted” on the FCCSCI server, in a subdirectory of your home directory named cs133/assignN, where N is the assignment number. (Note that both cs133 and assign are all in lower-case.) So the first thing we need to do is create this directory. Run these commands after you login to the server:

mkdir -p ~/cs133/assign0
cd ~/cs133/assign0

Each time we log back into the server to work on assignment 0, we’ll run the command

cd ~/cs133/assign0

which will place us in the assign0 subdirectory, ready to work on the assignment.

Like many assignments, this one has a template source code file you can start with. You can copy this file into the above directory with this command:

cp /usr/local/class/src/cs133/bag.hpp ~/cs133/assign0

You only need to do this once at the beginning, to start the assignment. After that, we want to edit this file, so we’ll run the command

micro bag.hpp

to open the source file bag.hpp in the Micro editor. At this point, we can start writing our code.

You can also download a copy of the bag.hpp file here.

The Bag data structure

The topic of assignment 0 (and of the first few lectures) is to review some core C++ concepts by implementing a “bag” data structure. A “bag” is a things which stores some values such that values can be added and removed, and you can loop over all the values currently in the bag. The bag can store duplicates (you can insert the same value more than once). What makes a bag interesting is not so much what it does, but what it doesn’t do: a bag does not guaranteed that the order of the values will stay the same as things are added and removed.

For example, suppose we create a bag (of capacity 10) and then insert the values 1, 2, 3 into it, in that order. The C++ code to do this with our not-yet-written bag class is

bag b(10); // Capacity = 10
b.insert(1);
b.insert(2);
b.insert(3);

If we now loop over the contents of the bag, we will get out the values 1, 2, 3, but not necessarily in that order. They might come out in any order. The bag class is not required to preserve the order the values were inserted in.

Contents of bag.hpp

The bag class we will be implementing looks like this (this is the contents of the bag.hpp file):

#pragma once
/*
 * bag.hpp
 * Definition of the `bag` class.
 */

class bag {
  public:

    /* bag(capacity)
       Constructs a bag with the given capacity (max. size).
    */
    bag(int c)
    {
        // Your code here
    }

    /* size()
       Returns the current size (number of elements) in the bag.

       NOTE: The minimum possible size is 0, the maximum is the capacity of the
       bag.
    */
    int size()
    {
        // Your code here (replace the return)
        return 0;
    }

    /* capacity()
       Returns the capacity (max. size) of the bag. 

       NOTE: Capacity is set at creation time and never changes after that.
    */
    int capacity()
    {
        // Your code here (replace the return)
        return 0;
    }

    /* empty()
       Returns true if the bag is empty (size is 0).
    */
    bool empty()
    {
        // Your code here (replace the return)
        return false;
    }

    /* full()
       Returns true if the bag is full (size equals capacity).
    */
    bool full()
    {
        // Your code here (replace the return)
        return false;
    }

    /* at(i)
       Returns the value of the i-th (index) element of the bag. i must be
       between 0 and size()-1, inclusive. If i is out of range, the function
       should return -10000000.
    */
    int at(int i)
    {
        // Your code here (replace the return)
        return -10000000;
    }

    /* exists(x)
       Returns true if the value `x` exists in the bag.

       NOTE: `x` is a *value*, not an *index*.
    */
    bool exists(int x)
    {
        // Your code here (replace the return)
        return false;
    }

    /* find(x)
       Returns the index at which the value `x` exists in the bag, if it 
       exists. If `x` does not exist, returns -1.
    */
    int find(int x)
    {
        // Your code here (replace the return)
        return -1;
    }

    /* insert(x)
       Adds `x` to the bag, unless the bag is full (if the bag is full, then
       `insert(x)` should do nothing).
    */
    void insert(int x)
    {
        // Your code here
    }

    /* erase(i)
       Erase the value in the bag at index `i`. If i is out-of-range, then
       `erase(i)` should do nothing.
    */
    void erase(int i)
    {
        // Your code here
    }

    /* remove(x)
       Remove the *value* `x` from the bag, if it exists. If `x` does not 
       exist in the bag, then `remove(x)` should do nothing. If there is
       more than one copy of `x` in the bag, then only one should be removed.
    */
    void remove(int x)
    {
        // Your code here
    }

  private:
    // Add whatever private members you need
};

You can find most of the details about how to implement the bag data structure in the lecture notes from the first two days of class.

Tracking changes in Git

Git is a version control system; it tracks different versions of a project’s source code files as they change. If you have a directory containing cpp and hpp source files, you can create a Git repository for that directory, and then every time you make a change, create a commit in Git. Later, you can view the complete history of all your commits, go back to any previous commit (no more commenting out code because you “might need it later”), etc.

All assignments are required to have their history tracked in Git; this is how I know that you actually wrote the assignment. When you start a new assignment, one of the first things you should do is create a new Git repository to track your work:

cd ~/cs133/assign0
git init

Then, whenever we add a file or make a change to our program, we want to do

git add bag.hpp
git commit -m "Message"

For the git add command, list the name(s) of the files you added or changed. You can also just do git add "*.[hc]pp to add all hpp/cpp files. git commit saves the current state of these files, along with a message describing what’s happening. Generally speaking, you should make a commit every time you do “something”: finish writing a function, pass an additional test, etc.

(One “feature” of Git that sometimes surprises people is that you have to re-add files every time you do a commit. If you do a git commit without doing a previous git add it will just complain that your commit is empty.)

Git is often associated with GitHub, but we’re not using GitHub here. Your assignment history is kept entirely local on the FCCSCI server. Thus you don’t need to worry about creating a GitHub account or pushing to remote, etc.

Remember: assignments without Git history will receive 0 credit, and you cannot add it after you’ve finished; you must commit your changes to Git as you work.

Compiling and testing our code

All assignments (except assignment 5) include a test runner, a provided .cpp file which defines int main() and tests your code (in the bag.hpp) to see if it does what it’s supposed to. This means that in most cases you should not write a main() function; one will be provided for you.

You can copy the assignment 0 test-runner source file into the assign0 directory with this command:

cp /usr/local/class/src/cs133/assign0_test.cpp ~/cs133/assign0

Or you can download a copy to your personal computer here.

To test your assignment submission, you have two options:

  1. Run the command test-assignment. This will compile and run your code together with the test-runner and report any failures to you. This is how I’ll test your code, so whatever test-assignment says is the grade you’ll get.

  2. Compile and run the test-runner manually. If you do this, you must be careful to compile and run the test-runner with the same compiler flags and debugging options that the test-assignment script uses.

The test-assignment script compiles all files with the following options:

-g -Werror=vla -Werror=return-type

The -g flag just adds debugging info to the program, so that if you need to look at in the debugger, you can. The other two flags turn things that would normally be compiler warnings into hard errors:

When the test-assignment script runs the test runner, it does two additional checks to look for memory errors:

All assignments except assignment 1 must be memory-safe: it is a fail for an assignment to leak memory, access memory not belong to the program (outside array bounds, etc.), etc.

The test-assignment script will also check for the presence of a Git history, and report the assignment as failing if it doesn’t have one.

Obviously, it’s easier to just run test-assignment than to try to replicate all that, but if you’re working on your own computer, that’s what you need to do to make sure the pass/fail results you see are consistent with what I’ll see when I go my grading.

Summary

If you’re following along in lecture, you should be able to write the bag class (two different versions of it) in bag.hpp and then get it to pass all the tests in the test-runner. And you should have a Git history which reflects the process of getting the bag class to the point where it passes all the tests. (You can view your Git history by running git log.)