COMP15 Project #1: Mathematical set abstract datatype

COMP 15 Project #1: Mathematical set abstract datatype

COMP15 Fall 20XX
Due: Thursday, February 3, 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 where the integers range from 0 to 127.

A set is represented using the "bit vector" technique where the set elements are encoded into the bits of one or more unsigned integers. Each bit stands for (represents) a single positive integer, starting from zero. If the bit is one, the corresponding positive integer is an element (member) of the set. In this case, individual bits in the vector are numbered from zero to 127. Thus, 127 is the largest positive integer that can be a member of a set and zero is the smallest.

Since only 32 bits can be represented in a single integer (an Intel IA-32 machine word), four integers are required to represent a set. These four integers are stored in a one-dimensional array. Bits within an integer are numbered sequentially from zero to 31, where bit zero is the least significant bit (LSB) and 31 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 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

Three files are provided:

bitset.h, which is the declaration of the BitSet class and its interface,
bitset.cpp, which is the definition of the BitSet class and the function main, and the
makefile to build the program.

These files will help get you started. 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 requirements to be satisfied:

The print method displays the elements of a set. Elements must be displayed on a single line, must be surrounded by curly braces and must be separated by a space. If integers 6, 5 and 0 are elements of the set, then print should display "{ 6 5 0 }" on a single line. You must adhere to this format as your output will be checked automatically.
Study the behavior of the unionOf function. It takes two sets as arguments and puts the union of the two sets into the current set (this object) which is the recipient of the call to unionOf. This approach makes the union operation look somewhat symmetric in its use. Follow this approach for the implementation of intersectionOf.
Add code to the function main to test the intersectionOf function. Read and follow the pattern used to test the unionOf function.
Proofread and correct any existing code, if necessary.

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.

The makefile will help you to build your program. To build your program, which is called "bitset", change the working directory to where your project files are stored and just type make on the command line. The make utility will read the makefile in the current working directory and will build bitset. We will discuss make and makefiles in more detail when preparing for the second project.

Extra challenges

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

Add a new set operation: isSubset.
Extend the BitSet implementation to accommodate finite sets of arbitrarily large size.

Of course, you must test what you build. Extra challenges are always above the call of duty and are for extra credit. Total extra credit is limited to a maximum of ten percent of the project points. This limit holds for all projects.

Account activation

Accounts have been created for pre-registered students. To enable your account, go to the URL http://www.eecs.tufts.edu/~accounts. 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 "p1", "p2", etc. For this project, you should submit your work using the command:

    provide comp15 p1 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 https://www.eecs.tufts.edu/gradebk. 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.

Information specification: BitSet

Here is an informal specification for the BitSet interface. You will need to build and test to this specification.

Function: BitSet() ;
  Purpose: Creates a new BitSet object and initializes it to the
    empty state
  Parameters:
    None
  Returns:
    Nothing
  Side-effects:
    Changes the elements array
  Error conditions:
    None

Function: bool isElement(int i) ;
  Purpose: Determines if the positive integer i is an element (member)
    of the mathematical set represented by the object
  Parameters:
    i: Positive integer value to be tested; The value provided by the
       caller could be out of the allowed range of integer values that
       can be represented in the bit set
  Returns:
    Returns true if i is an element of the set; returns false if
    i is not an element of the set
  Side-effects:
    None
  Error conditions:
    To be determined (TBD) by you!

Function: void addElement(int i) ;
  Purpose: Adds the positive integer i to the mathematical set, that is,
    the positive integer i will become an element of the set
  Parameters:
    i: Positive integer value to be added to the set. The value
       provided by the caller could be out of the allowed range of
       integer values that can be represented in the bit set
  Returns:
    Nothing
  Side-effects:
    Changes the elements array
  Error conditions:
    To be determined (TBD) by you!

Function: void removeElement(int i) ;
  Purpose: Removes the positive integer i from the mathematical set,
    that is, the positive integer i will no longer be an element of the set
  Parameters:
    i: Positive integer value to be removed from the set. The value
       provided by the caller could be out of the allowed range of
       integer values that can be represented in the bit set
  Returns:
    Nothing
  Side-effects:
    Changes the elements array
  Error conditions:
    To be determined (TBD) by you!

Function: void print() ;
  Purpose: Displays the current elements of the set in a readable form
    using standard set notation, e.g., { 0 3 4 7 8 }. Please follow
    this format exactly.
  Parameters:
    None
  Returns:
    Nothing
  Side-effects:
    None
  Error conditions:
    None

Function: void clear() ;
  Purpose: Clears the set and makes it empty
  Parameters:
    None
  Returns:
    Nothing
  Side-effects:
    Changes the elements array
  Error conditions:
    None

Function: bool isEmpty() ;
  Purpose: Tests the current set to see if it's empty
  Parameters:
    None
  Returns:
    True if the set is empty; false if the set is not empty
  Side-effects:
    None
  Error conditions:
    None

Function: bool isEqualTo(const BitSet &a) ;
  Purpose: Tests the current set to see if it is equal to the set given
    as a parameter; Equality means "has exactly the same elements."
  Parameters:
    a: Set operand (a reference parameter)
  Returns:
    True if the set a is equal to the current set; false if the set a
    is not equal to the current set
  Side-effects:
    None
  Error conditions:
    None

Function: void unionOf(const BitSet &a, const BitSet &b) ;
  Purpose: Forms the union of the two argument sets and stores the result
    in the current BitSet object, i.e., the elements (members) of the
    current BitSet object will contain the union of the two sets
  Parameters:
    a: First set operand to the union operation (a reference parameter)
    b: Second set operand to the union operation (a reference parameter)
  Returns:
    Nothing
  Side-effects:
    Changes the elements array
  Error conditions:
    To be determined (TBD) by you!

Function: void intersectionOf(const BitSet &a, const BitSet &b) ;
  Purpose: Forms the intersection of the two argument sets and stores the
    result in the current BitSet object, i.e., the elements (members) of the
    current BitSet object will contain the intersection of the two sets
  Parameters:
    a: First set operand to the intersection operation (a reference parameter)
    b: Second set operand to the intersection operation (a reference parameter)
  Returns:
    Nothing
  Side-effects:
    Changes the elements array
  Error conditions:
    To be determined (TBD) by you!