User:Jason.wilkins/Laboratory for Sets

From A-State Computer Science Wiki
Revision as of 10:43, 19 April 2010 by Jason.wilkins (Talk | contribs)

Jump to: navigation, search

A portion of this lab is to be done during the scheduled lab time. The take-home programming assignment is to be turned in before the next lab; see the lab website. The in-lab portion is worth 40% of the lab credit; the programming assignment is worth the other 60%. See the website for details on how the programming assignment will be graded. You are not responsible for user errors in input unless specified in the assignment. Feedback will be provided explaining your grade on each assignment.

It is important that you complete each step before going on to the next, as the exercises build upon one another. You will find it helpful to diagram the action of each method or function as you go along. If you have difficulty in some step, DO NOT proceed before resolving it; seek assistance from your lab proctor. You will not be able to fully appreciate the remaining content of the lab and you are likely to compound the problem.


In this lab a Set class is developed using the skills learned in previous labs. The instructions given here are less specific and intended more as general guidance.

Topics Covered in this Lab:
  • Sets
  • Set operations
Questions Answered in this Lab:
  • What is a set?
  • How might a set class be designed for C++?
  • What operations can be performed with sets?
  • How might set operations be implemented as part of a class?
Demonstrable Skills Acquired in this Lab:
  • An understanding of sets and set operations
  • How one might implement a class given less specific instructions
Createproject.pngCreate a project oop14iL


A set is a collection of mathematical objects (As used in mathematics, object is just a way to say "thing", so a set is a collection of things. This is a distinct idea from C++ objects.). A mathematical object is either a member of a set or not, so it does not make sense for an object to be in a set more than once. However, an object can be a member of multiple sets at once. Sets are themselves consider to be mathematical objects, so it is possible to have sets that contain other sets.

To avoid ambiguity, from this point mathematical objects spoken of in relation to sets will be called elements from this point onward.

Sets are commonly denoted by using curly braces in one of two ways. The first is to exhaustively list every element of a set within the curly braces. For example, the set containing the integers between 1 and 10 could be written as \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}. However most sets are too large to define this way and may even contain an infinite number of elements and are denoted using what is referred to as set builder notation. An example would be all even integers which can be written as \{x|\text{where }k \in \mathbb{I}, x = 2k\}, and which is read as "x such that where k is an integer, x is two times k." Sometimes, infinite sets are more intuitively denoted by using ellipsis, for example, all integers could be written { \dots , -2, -1, 0, 1, 2, \dots } and even integers as { \dots , -4, -2, 0, 2, 4, \dots }.

The "\in" operator, pronounced "element of," used in the previous example is a relational operator that is not built into C++. It returns true if the element given on the left is a member of the set given on the right. Also mentioned in the previous example is the the set of all integers which is so commonly used that it has a shorthand notation "\mathbb{I}."

The set containing all the mathematical objects under consideration is called the universe. For example, if the real numbers are being considered then the universe is the infinite set \mathbb{R} containing all reals.


  • Sets are collections of elements.
  • Each given element is either is a member or not a member of a given set.
  • The relational operator "\in" and "\notin" are used to test set membership.
  • An element cannot appear in a set twice.
  • An element can be in more than one set at once.
  • A set is denoted using curly braces
  • Infinite sets are

More information about sets can be found on the Internet.

  • Wikipedia [1]
  • Wolfram MathWorld [2]

Implementing a Set Class

The universe can be limited to a finite set and for simplicity for the rest of this lab we are only going to consider the very small set of capital letters from A to G.

Verbatimcode.pngCode Illustration
   int a [100];
   int size = 0;
   cout << "Enter an integer (-1 to end): ";
   std::istream_iterator <int> input (cin);
   while (*input != -1)  // dereference
      a[size++] = *input;  // dereference
      cout << "Enter an integer (-1 to end): ";
      input++;  // increment
   }  // end while

Notice how iterator input is associated with input stream cin. Notice also how input is dereferenced and incremented as a pointer variable might be in a conventional C++ program.

Add a short loop to function main to print the contents of array a to the standard output cout; print one space between each pair of values.

Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate this output for the lab instructor.

The STL Algorithm

An STL algorithm can be used to print the contents of the array as well; add an include for the header file algorithm to file master.h and add the following to function main.

Verbatimcode.pngCode Illustration
   std::ostream_iterator <int> output (cout, " ");
   std::copy (a, a+size, output);
   cout << endl;

The STL algorithm copy will move everything from the location specified in the first parameter up to, but not including, the location specified in its second parameter to its third parameter. Since a is the name of an array, it is essentially the address of the first array element; the addition of size to a results in a location one past the last element stored in a. Notice how iterator output is associated with cout; the character-string parameter specifies what should be written between values.

The STL Container

An STL container can be used to store and manipulate data. In particular, the STL vector container can be used where an array might be used in a conventional C++ program. Add an include for the header file vector to file master.h and add the following to function main.

Verbatimcode.pngCode Illustration
   std::vector <int> v;
   cout << "\n\nEnter # for max subsequence search (-999 to end): ";
   std::istream_iterator <int> input2 (cin);
   while (*input2 != -999)
      v.push_back (*input2);
      cout << "Enter # for max subsequence search (-999 to end): ";
   }  // end while

The STL vector object v will be filled with numbers from the keyboard via another istream_iterator object, input2. The vector member function push_back is used to add data to the end of its object.

The values stored in a vector may be manipulated using an iterator. Add the following to function main.

Verbatimcode.pngCode Illustration
   std::vector<int>::const_iterator vIndx;
   for (vIndx = v.begin(); vIndx != v.end(); vIndx++)
      cout << *vIndx << ' ';
   cout << endl;

The vector member function begin returns a reference to the first item in the container; function end returns a reference to just past the last item in the container, hence the use of the != operator.

The same effect may be achieved with the copy algorithm; add the following to function main.

Verbatimcode.pngCode Illustration
   std::copy (v.begin(), v.end(), output);
   cout << endl;

Note here again how copy uses references to the first item and one past the last item in the container. FOR IN-LAB CREDIT: Demonstrate the results of copy for the lab instructor.

Example Problem: Maximal Subsequence

Consider now the problem of finding the subsequence in a series of values whose sum is maximal. A vector will be used to implement a search for this subsequence. A brute-force algorithm is developed here; a more elegant solution is to be devised in the homework.

Consider for example a sequence of five values: a_1, a_2, a_3, a_4 and a_5. There are five subsequences starting with a_1, and each of their sums must be considered: a_1 by itself, a_1 + a_2, a_1 + a_2 + a_3, a_1 + a_2 + a_3 + a_4, and a_1 + a_2 + a_3 + a_4 + a_5. Similarly, there are four subsequences starting with a_2, three with a_3, two with a_4 and just one with a_5 (a_5 by itself). In general, there will be n + (n-1) + (n-2) + \ldots + 1 = n(n+1)/2 subsequences to consider for n values. A nested loop can be written to generate these subsequences; the outer loop will keep track of the starting location while the inner loop keeps track of the ending location. Two iterators shall be used for this purpose. Add the following to function main.

Verbatimcode.pngCode Illustration
   std::vector <int>::const_iterator beginIndx;
   std::vector <int>::const_iterator endIndx;

   for (beginIndx = v.begin(); beginIndx != v.end(); beginIndx++)
      for (endIndx = beginIndx; endIndx != v.end(); endIndx++)
         // body;

The body of this loop must use another iterator, e. g., sumIndx, to move between beginIndx and endIndx, summing the elements between them. This sum should be compared to a running maximum sum; if it is found to be greater than the current maximum, the sum should be stored as the new maximum and the current beginning and ending indices should be saved. This being done, the results can be displayed with the following addition to function main.

Verbatimcode.pngCode Illustration
   cout << "maximal subsequence is ";
   std::copy (maxBeginIndx, maxEndIndx+1, output);
   cout << endl;

The iterators maxBeginIndx and maxEndIndx in the above code fragment are defined like beginIndx and endIndx in the preceding fragment. Note that maxEndIndx+1 is passed to algorithm copy here since copy always expects an ending location one past the last value to be copied.

Execute the program and verify that it is working correctly.

Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate the algorithm for input of the lab instructor's choosing.

Labsubmitsinglefile.png FOR IN-LAB CREDIT: Zip up these files:
Name the file {{{zip}}} and upload to CSCADE.