CPSC 333: Assignment #5

Location: [CPSC 333] [Assignments] Assignment #5

This page was most recently modified on April 7, 1997.


Problem Statement

This assignment is to be prepared and submitted by groups of at most four students - preferably, who are all in the same lab section. Each group of students should submit one copy of their solution.

The assignment is due at 11:59 pm on Thursday, April 17.

A marking scheme for this assignment hasn't been set yet. However, Question #1 will be worth at least twice as much (and not more than four times as much) as Question #2.

  1. The directory

    ~eberly/CPSC333/A5

    contains source code in a file, ``buggy_match.cpp,'' which can be compiled using CC. This is source code for a program that is supposed to prompt you for a ``source'' string that can be up to 50 characters long, and a ``pattern'' string that can have length up to 20, and then either report the position of (the beginning of) the last occurrence of the pattern in the source string, or report that the pattern isn't found in the source. A slightly more description of the requirements for this program can be found at the beginning of the source code.

    A version of this source code can also be viewed. However, this version has been edited to ensure that it can be viewed correctly using a web browser. Thus, the file contained in the above directory should be copied and used, instead, for work on this question.

    Sadly, this ``matching'' program is a bit ``buggy,'' because a certain fiendish instructor (whose name needn't be mentioned) has seeded errors into it before making it generally available. If you don't believe this, compile the program yourself using CC and try it out!

    The source code includes a main function and two functions that this calls - ``myGetString,'' which reads a string of up to some given maximum length from the input line and then flushes the rest of the input, and ``isPrefix,'' which checks whether a given pattern string appears starting at a given position in a given source string.

    1. Apply the ``unit testing'' methods described in lectures, in order to design a set of tests for the main module of this program. You answer should include a flow graph and a set of tests that you'd develop using ``path testing,'' ``condition testing,'' and ``loop testing.''

    2. Now, execute these tests on the main function. List the output that is obtained for each, and document any errors in the source code that you discovered as a result of this, along with corrections you'd make in order to eliminate them.

      You will either need to use a debugger, or write a bit of testing code (to produce ``stubs'' replacing the functions that the main module calls), or both, in order to answer this part of the question.

      You may also design additional tests, or use additional methods in order to look for errors, if you wish to. For example, simply reading the source code carefully can sometimes uncover errors that would otherwise be missed. If you find additional errors in this way, please report them, along with the methods you used to find them. (However, discussing this process with students that aren't in your own group still isn't allowed.)

    3. Now perform unit testing on both of the other functions in this program. The documentation appearing in the source code before each function should be used as a reference, in order to determine what each function is supposed to do.

      Keep your answer for this part of the question briefer than your answer for the earlier parts. In particular, you don't need to describe a ``complete'' suite of tests. However, you should mention any tests you performed that ``succeeded'' in finding errors, the errors in the source code that you discovered, and the corrections you made in order to eliminate them.

      You'll need to use a debugger, or write a bit of testing code, in order to answer this question, as well. In particular, you'll probably need to write one or more ``drivers'' that call the functions you're testing.

      Finally, don't be frustrated if you don't find any errors for one or more of these functions. To the knowledge of the instructor, one of these functions might actually be correct!

    4. Next, perform ``system integration'' and ``integration testing'' in order to assemble the system from the components you've unit tested.

      If you use ``top down'' integration then you can do this by gradually replacing the ``stubs'' you used to unit test the main module with the functions corresponding to them. The tests you developed (and the test results you obtained) to unit test the main module will probably be useful again, here.

      Keep your answer for this part of the question brief: Make sure to mention the order in which you combined functions together in order to form subsystems. Describe any tests you used that were useful for detecting errors (if any errors remained to be found), and describe the errors you found as well as the changes made to the source code in order to eliminate them.

      Of course, you should also perform (and briefly document) ``regression testing'' if you found errors during system integration and changed functions in order to eliminate them.

    5. Finally, hand in source code for a ``corrected'' version of this program. For this part only, you should use the submit facility, to electronically submit a text file containing the source code.

      This will be assessed (in part) by using diff to compare it to the source code you started with - so, please, submit a file that only includes changes made to correct errors (and not additional code inserted for testing purposes, etc.).

      The submit facility will be configured so that you can use it for CPSC 333 during the last week of classes (but, probably, not before then).

      Final Hint: If you found no errors in the source code, or only one, then you should keep looking for more. If you found more than six or seven, then you've found more than the instructor knows about (and you should consider checking whether some of the ``errors'' you found were really errors at all).

  2. The above directory also contains a header file

    my_stack.h

    including the declarations needed to define a simple version of a ``stack'' class, along with an object file obtained by compiling source code,

    my_stack.o

    along with a source file for a main program that presents a simple menu that can be used to select operations,

    stack_ops.cpp

    and, finally, an executable program that was obtained by compiling stack_ops.cpp (along with my_stack.o),

    stack_ops

    In order to simplify debugging, the stack interface includes a ``list'' function, which correctly displays the number of elements currently on the stack and lists the contents, in order from bottom element to top. To the best of my knowledge, this interface function, and the main module I've provided you with (in stack_ops), are both correct. In the case of the interface function, this means that its implementation is consistent with the declaration of the function that's given in my_stack.h.

    On the other hand, two errors have been seeded into the source file ``my_stack.cpp'' that was compiled in order to generate the object file, my_stack.o.

    Design a set of tests that can be applied to this ``stack'' class, treating the list function that's something that has only been introduced for testing purposes (so that it will be made private, or perhaps deleted, before production code is produced), but assuming that all the other functions in the interface must be tested. You'll have to use ``black box'' testing methods - that is, you'll have to design tests using only the header file ``my_stack.h'', because the source code for the implementation isn't being supplied.

    Don't give these tests in detail, as an answer for this question. Instead, just describe the kinds of ``cases'' you tried to cover. For include, mention the fact that you included a test for ``An attempt to pop an element when the stack was empty,'' rather than listing the sequence of stack functions you called, etc. for such a test.

    Then, try to locate the errors as precisely as you can: Identify the interface function (or functions) containing them, describe the output value(s) that is (are) incorrect, and say how, and say whether the stack is correctly changed when the function is called, or not.

    Once again, you may assume that the ``list'' function works correctly, so you don't need to write or compile any code in order to answer this question. However, you may write a new main module, to replace the one that's been provided, if you wish to.

Location: [CPSC 333] [Assignments] Assignment #5


Department of Computer Science
University of Calgary

Office: (403) 220-5073
Fax: (403) 284-4707

eberly@cpsc.ucalgary.ca