Data Structures and Algorithms

Feedback from assignment 3

  1. Separating the classes

    Many of you failed to place each class in a separate file!

    This allows:

    1. separate development - once the specification is decided, you can individually work on separate parts of the whole problem,

    2. separate verification - each class can be verified independently of the others.

      Of course, sometimes one class depends on another, so complete independence can't be achieved. However the testing strategy becomes crystal clear, test all the classes which don't depend on any others first, then test classes that only depend on this first group, and so on.

  2. Equivalence Classes

    Very few of you had any decent approach to proving individual methods of classes correct.

    Some were trivial .. simply put some data in an object and verify that you could get it back! Such tests can be performed entirely automatically: the program sets the object's attributes and compares the values returned by 'projector' functions. By using a program for this, you make use of the machine's ability to mechanically compare large amounts of data accurately (once the test program is correct, of course!).

    Generally, there will be large number of equivalence classes - and therefore test cases. These can be handled in three ways:

    1. Use program code to generate the test data sets. For instance you want to test 0,1,2,...,n,n+1 items where the items are random numbers. Write a function to generate the appropriately sized arrays of random numbers.

    2. Use data structures to hold the tests. For example, node labels - make an array of strings:
      char *labels[] = { "a", "aa", "aaa", "b", "" };
      #define N_LABELS	(sizeof(labels)/sizeof(char *)) 
      Note how C allows you to put an arbitrary number of items in an array, using [], and #define a symbol which gives the number of items. This means that as you discover a need for more tests, they are trivially added to labels and no other part of the program needs changing!

    3. Put the test data in files - prepared with a text editor, or another program. This would be a good approach for testing the MST itself
      • determine what cases need testing,
      • produce a number of files with the appropriate data in them,
      • run the program reading from each file in turn (give the files names like "graph1", "graph2", etc, so that a program can automatically read them all!) or
      • write a Unix shell script to run the program with each file as input and capture the test output.

  3. Presenting Verification Results

    The best way to do this is with a table:


    Brief description
    of equivalence class

    • Value of data,
    • Name of test file,
    • Name of data set,
    • etc
    • Location,
    • Name of proram
    • Name of function
    No data - no_data.cAssertion
    Empty data
    - null_data.cNULL
    n > max 106 large_n.cAssertion
    Single datumdata_1testx.cSame data
    2 points
    out of order
    2 points
    in order

    Some examples of the sorts of entries that could be made in each column are shown.

    You can obviously vary the columns (particularly the second and third) to suit the style of test that you are making.

    Table of Contents
    © John Morris, 1996