User:Jason.wilkins/Laboratory for Sets

From A-State Computer Science Wiki
Revision as of 10:08, 19 April 2010 by Jason.wilkins (Talk | contribs) (Created page with '{{Lab Instructions}} =Introduction= In this lab a <tt>Set</tt> class is developed using the skills learned in previous labs. The instructions given here are less specific and …')

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.

Introduction

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

Sets

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

More information about sets can be found on the Internet.



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): ";
      ++input2;
   }  // 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: oop13iL.zip
Name the file {{{zip}}} and upload to CSCADE.