COMP 15 Project #1: Bit set abstract datatype

COMP15 Fall 20XX
Due: Wednesday, September 22, 11:00PM


Many data structures have their basis in formal mathematics. In this assignment, you will build and test an abstract data type -- a C++ class -- to represent and manipulate small, finite sets of positive integers. Sets will be represented using the "bit set" technique where the set members are encoded into the bits of an unsigned integer. Each bit in the integer that represents the set stands for a single positive integer, starting from zero. Individual bits in the set are numbered from zero to N, where N is the size of the set. (The set size is stored as part of the C++ class.) Thus, N-1 is the largest positive integer that can be a member of the set and zero is the smallest. Bits are numbered sequentially from zero to N-1 where bit zero is the least significant bit (LSB) and N-1 is the most significant bit (MSB.) This is also the correspondence from bit to positive integer. The figure below illustrates the bit numbering and mapping for an 8-bit (8 element) set.

7 6 5 4 3 2 1 0

Bit zero at the far right is the LSB and bit seven at the far left hand side is the MSB.


The objectives for this project are:

You will need all of these skills in future project assignments.

What needs to be done

Two files are provided: bitset.h, which is the declaration of the BitSet class and its interface, and bitset.cpp, which is the definition of the BitSet class and the function main. These two files will help get you started with C++. You need to copy these files from the dirctory /g/15/class/project1 to your own working directory and read through the existing implementation to get more information.

The existing implementation is incomplete. You will need to add new method functions to fully implement the interface. Here are some additional requirements to be satisfied:

You should test as thoroughly as possible, but avoid exhaustive testing. Identify and test any special cases. Add comments to the source code to describe your approach and solution. Don't forget to fill out the header comments with your name, section and e-mail address.

Extra challenges

Once you have completed the basic assignment, here are some extra things to try.

Of course, you must test what you build. Extra challenges are always above the call of duty and are for extra credit.

Account activation

Accounts have been created for pre-registered students. To enable your account, go to the URL MISSING LINK. You will need to supply your Tufts e-mail login name and password to activate your account. If you do not have a Tufts e-mail login name or if you have a problem with account activation, please see a member of the system staff in Halligan Hall Room 231C.

Submitting your work

We will be using the CS Department's provide system to submit finished programs. The provide command syntax is:

    provide comp15 <assignment> <files>
Projects assignments are labelled "a1", "a2", etc. For this project, you should submit your work using the command:
    provide comp15 a1 bitset.h bitset.cpp
Be sure you are completely satisfied with your work before submitting!

Checking evaluations and scores

This semester we will be using the gradebk web service to keep track of evaluations and scores. The URL for gradebk is MISSING LINK. Please check your evaluations within the two week period after your work has been reviewed and the evaluation has been posted. Issues will not be considered after the two week period has expired.

Copyright © 2004-2013 Paul J. Drongowski