Project 2

Due: Thursday, October 15, 2015 9:00PM


The objectives of this project are 1) to practice using C++ class syntax, 2) to practice using C++ vector and string classes.


For this project, you will implement member functions of a C++ class that stores sets of strings. You will use the C++ vector class to store the set. (More on this below.) This class will represent not just finite sets of strings, but also some infinite sets of strings. In particular, objects in this class can represent cofinite sets. A set is cofinite if its complement is finite. For example, the subset of natural numbers { 1, 5, 7, 8, 9, 10, 11, ...} is cofinite because it is the complement of the set { 0, 2, 3, 4, 6}. In C++, we can represent a cofinite set by storing its complement and an additional boolean value to indicate that we really want the complement of the stored values.

It turns out that if two sets A and B are either finite or cofinite, then their union, intersection and complements must also be finite or cofinite. For this project, you will implement member functions that will create the union, intersection and complements of finite and cofinite sets of strings. You will also implement functions to compute the membership and subset relations.


Your assignment is to implement the member functions of the class SoS (short for "Set of Strings") defined below. Each SoS object has two data members: m_cofinite, m_vos. The value of m_cofinite is true if the object represents a cofinite set. The vector object m_vos has the strings in the representation. These are either the strings that are in a finite set or the strings that are not in a cofinite set. (For now you can think of a vector as an array. They behave very much like lists in Python or ArrayLists in Java. Section 7.3 of the textbook has an introduction to vectors.) These should be the only data members you need. The requirements for each member function is described below.

class SoS { public: // Do not change the member function prototypes for // any public member function. // See documentation in Project 2 description. SoS() ; void insert(string str) ; void print() const ; bool isMember(string str) const ; bool isSubset(const SoS& B) const ; bool isFinite() const ; SoS makeComplement() const ; SoS makeUnion(const SoS& B) const ; SoS makeIntersection(const SoS& B) const ; // The function dump() is used for grading. Do not modify! // vector<string> dump() const { return m_vos; } private: // Do not change the types of these private data members bool m_cofinite ; vector<string> m_vos ; // vos = vector of strings // Declarations for Additional private member functions // may be added below. Fully document these. } ;

Here are the requirements for each member function.

Implementation Issues

Here are some issues to consider and pitfalls to avoid. (You should read these before coding!)

Submitting your program

You should submit these files to the proj2 subdirectory: If you followed the directions in setting up shared directories, then you can copy your code to the submission directory with: cp sos.h sos.cpp mytest.cpp ~/cs202proj/proj2/ You can check that your program compiles and runs in the proj2 directory, but please clean up any .o and executable files. Again, do not develop your code in this directory and you should not have the only copy of your program here.