Data Structures and Algorithms

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:

   Class Brief description of equivalence class	Representative Value of data, Name of test file, Name of data set, etc	Test Location, Name of proram Name of function	Expected Result	Result
   No data	-	no_data.c	Assertion raised	Assertion raised
   Empty data set	-	null_data.c	NULL return	NULL
   n > max	106	large_n.c	Assertion raised	Assertion raised
   Single datum	data_1	testx.c	Same data returned	OK
   2 points out of order	data_2_out	testx.c	Order reversed	OK
   2 points in order	data_2_in	testx.c	Order unchanged	OK

   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