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:

- 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.

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.

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.

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.

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 "

provide comp15 a1 bitset.h bitset.cppBe sure you are completely satisfied with your work before submitting!

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.