UCR CS 14: Introduction to Data Structures and Algorithms

Spring Quarter 2003 / Class webpage

Lab 03

Remember, in this course, all programming will be done under the Linux operating system, using standard programming tools for that environment. Linux is a free operating system, available for all to download (RH), (Mandrake) and use with no cost. Linux itself is about a decade old, but in conjunction with a set of free utilities from the GNU project, behaves like a member of the UNIX family of operating systems.

Tutorials on Linux are available all over the Internet, Google for "Linux tutorial" and find one that suits you, or just try this one.

Also, we will be grading your programs with the -Wall -Werror compilation options, as always. If your program does not compile with these flags, it will not be evaluated.

In this lab, we will work with testing.

"Thinking about potential problems as you code is a good start. Systematic testing, from easy tests to elaborate ones, helps ensure that programs begin life working correctly and remain correct as they grow. Automation helps to eliminate manual processes and encourages extensive testing. And there are plenty tricks of the trade that programmers have learned from experience" *.

With this in mind, your task is test and correct the codes below (code style and user interface also collaborate to your grade).

Turn-in

First, you download the file weirdcounter which contains an implementation of the Counter interface.

Your task is to develop a test driver according to the specification of ADT Counter given in Figure 1.


Figure 1

That is, write a file testweird.cc with a main function that creates WeirdCounter objects and calls their functions in order to determine whether the class is indeed an implementation of the ADT Counter. Do not look at the source code for WeirdCounter!

Finally, keep in mind that now you have to develop the program that uses the ADT Counter through the class WeirdCounter, as illustrated in Figure 2.


Figure 2

Hints: You are allowed to use last week's test driver testcounter.cc as a starting point, but you should remember that it contains only a few of the necessary test cases. Also, it might be useful to define additional functions besides main to avoid repetitive code.

Miscellaneous Tasks

1 point possible

Attendance for the full lab period is mandatory. Try working on some of the following short tasks.

For each of the code fragments below [(a), (b), ... , (f)], test its boundary cases and then fix the code if you find that it fails your tests. Do NOT rewrite the whole code. Instead, just correct the errors.

By "testing the boundary cases" I mean the following. Suppose, for example, that you instantiate a Counter with a min value of -1 and a max value of 3. These are the boundary values, so if you were to try to set the counter's value to -2 you should get an exception. If you don't then you know that the Counter was implemented incorrectly.

You should write the answer to each problem (from (a) to (f)) in a separate file. Also, these are just code segments, you are supposed to write the complete code, with input and output processing. Name your files lab3a.cc, lab3b.cc, and so on, and make sure to submit them all in the same turnin directory.

Use exception control when necessary!

(a) This is supposed to compute factorials (0.2 points):

int factorial (int n)
{
   int fac;
   fac = 1;
   while (n--)
       fac *= n;
   return fac;
}

(b) This is supposed to print the characters of a string one per line (0.2 points):

i = 0;
do
{
   putchar(s[i++]);
   putchar('\n');
}
while (s[i] != '\0');

(c) This is meant to copy a string from source to destination (0.2 points):

void strcpy (char *dest, char *src)
{
   int i;
   for (i = 0; src[i] != '\0'; i++)
       dest[i] = src[i];
}

(d) This function is supposed to sum the first n elements of an array. Ask the array elements to the user, consider an array with five elements (0.2 points):

int sumArray (int anArray[], int n)
{
   int s, i;
   for (i = 0; i < n; i++)
       s += anArray[i];
   return s;
}

(e) A character class test (0.2 points):

if (c >= 'A' && c <= 'Z')
{
   if (c <= 'L')
         cout << "first half of alphabet";
   else
         cout << "second half of alphabet";
}

Bonus, more 0.4 points

(f) Calculate the next day.
Also, define function main which asks for a date and outputs the next day.
Save your file as lab3_2f.cc.
Hint: isLeapYear and const are right.

const int MONTHS_PER_YEAR = 12;
const int DAYS_PER_MONTH[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeapYear(int year)
{
   // Example: 2000 is a leap year but 1900 was not
   return ((year % 400 == 0) ||
      ((year % 4 == 0) && (year % 100 != 0)));
}

void incrementDate( int& month, int& day, int& year)
{
   day++;
   if( day > DAYS_PER_MONTH[month - 1])
   {
      // test for February 29
      if( month == 2 && isLeapYear(year) && day == 29)
         return;
      else
      {
         day = 1;
         month++;

         if( month > MONTHS_PER_YEAR)
         {
            month = 1;
            year++;
         }
      }
   }
}

Hints and considerations

1. Test as you write the code

• Test code at its boundaries
• Test pre- and post-conditions
• Use assertions
• Program defensively
• Check error returns

2. Systematic testing

• Test incrementally
• Test simple parts first
• Know what output to expect
• Verify conservation properties
• Compare independent implementations
• Measure test coverage

3. Test automation

• Automate regression testing
• Create self-contained tests

4. Test scaffolds

• Test a component in isolation. It's easy to build scaffolds for testing mathematical functions, string functions, sort routines, and so on, since the scaffolding is likely to consist mostly of setting up input parameters, calling the functions to be tested, then checking the results. It's a bigger job to create scaffolding for testing a partly-completed program.

5. Stress tests

• High volumes of machine-generated input. Machine-generated input stresses programs differently than input written by people does. Higher volume in itself tends to break things because very large inputs cause overflow of input buffers, arrays, and counters, and are effective at finding unchecked fixed-size storage within a program.

For more details, check:
   * KERNIGHAN, B.W., PIKE, R. The Practice of Programming. Addison-Wesley 1999.

Did you know?

Software testing is an important research area inside Computer Science. That is, there is a lot of people concerned about improving software quality by refining test techniques. Here are some reading suggestions if you have any interest/curiosity in knowing what some people do.

Papers

• Thompson, H.H., Whittaker, J.A., Mottay, F.E. Computer security: Software security vulnerability testing in hostile environments. Proceedings of the 2002 ACM symposium on Applied computing. March 2002.
• Sinha, S., Harrold, M.J. Analysis and Testing of Programs with Exception-Handling Constructs. IEEE Transactions on Software Engineering, vol. 26, no. 9, pp. 849-871, September 2000.
• Rothermel, G., Harrold, M.J., Dedhia. J. Regression Testing for C++ Software. Journal of Software Testing, Verification, and Reliability, vol. 10, no. 6, June 2000.
• Harrold, M. J. Testing: A roadmap. 22th International Conference on Software Engineering, jun. 2000.

Books

• Tamres, L. Introducing Software Testing. Addison Wesley, 2002.
• Binder, R. V. Testing Object-Oriented Systems: Models, Patterns, and Tools. Addison Wesley Longman, Inc., 1999.