# 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:

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.cAssertion
raised
Assertion
raised
Empty data
set
- null_data.cNULL
return
NULL
n > max 106 large_n.cAssertion
raised
Assertion
raised
Single datumdata_1testx.cSame data
returned
OK
2 points
out of order
data_2_outtestx.cOrder
reversed
OK
2 points
in order
data_2_intestx.cOrder
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.