COMP15 Project #1: Bit set abstract datatype

COMP 15 Project #1: Bit set abstract datatype

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

Overview

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.

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

Objectives

The objectives for this project are:

To learn the form of a C++ program and to extend an existing class with new functionality.
To learn about and apply the C++ standard output stream.
To learn about the internal representation of integers and bit twiddling in C++.
To become familiar and functional with the laboratory environment and its tools (the Emacs editor, the g++ compiler and so forth.)
To begin to think systematically about program testing.

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:

The print method displays the members of a set. If bits numbered 6, 5 and 0 are one and all other bits are clear, then print should display "{ 6 5 0 }" on a single line.
Study the behavior of the setIntersection function. It takes two sets as arguments and puts the intersection of the two sets into the current set (this object) which is the recipient of the call to setIntersection. This approach makes the intersection operation look somewhat symmetric in its use. Follow this approach for the implementation of setUnion.
Handle set sizes correctly. Proofread and correct any existing code, if necessary.
Add code to the function main to test your new functions.

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.

Add a new set operation like isSubset.
Extend the BitSet implementation to accommodate finite sets of larger size. Try extending size to long long unsigned int. For the really courageous, implement really big bit sets using an array of integers.

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.