Introduction to Algorithms - Tester

Paul Taylor

Janaury 2001

This course is about components, not whole programs: you will be writing and testing single methods to do sorting and searching. The main() method that provides the "whole program" and calls your method is in the TESTER.

1 Aims of the TESTER

To give students immediate feedback on whether they are achieving the objectives of the exercises.
To monitor the rate of progress of the class of students as a whole, i.e. that I may pass on to the next topic when 60% have achieved the objectives of this one.
To monitor whether individual students are participating as required in the exercises and lab sessions.
To teach complexity in an empirical way.
To teach trip testing as a verification technique: a program ( JAVA class file) is to consist not only of the code, but also the informal specification in English, the formal logical specification and correctness proof, and test data. (The term trip test was introduced by Donald Knuth for debugging T_EX and verifying subsequent versions and implementations.) (This has not been implemented.)

2 Disclaimers

This is not an automated marking tool and will not be used as such.
The monitoring of students is not secure.
Only the principal versions of the core exercises in the course are covered.

3 Objectives

The TESTER

provides a main() so that you only write the relevant code;
provides arguments (either explicitly or randomly) to your method and prints out the results;
provides a Trace.print() method for you to use (instead of System.out.print()) for debugging and observing loop invariants; it is enabled or disabled from the command line;
does thorough trip-testing of your method and prints (and logs) a report;
does time-complexity testing, reporting the coefficients of the best-fitting curve, and drawing it for you (using gnuplot).

Later versions of the TESTER will

provide animation, profiling and a GUI;
run your own trip tester both on your code and on a supplied collection of correct and incorrect algorithms.

4 Using the TESTER

The TESTER can

run your method once with random or specified arguments,
trace its behaviour, or
check that it is correct and time how long it takes.

These three commands (run, trace and check) are provided in the directory DCS127 in which you are to do your work for this course. They are not standard Linux commands and will not work elsewhere.

The run and trace commands compile your class before running it, as there are some complicated extra arguments that have to be given to javac to make it connect your class with the TESTER.

The check command does not compile your class first. This is to make you do some individual runs before the comprehensive test.

Do not use the javac and java commands directly.

You invoke the TESTER by typing commands such as

run Linear.java
trace Linear.java size=15 strictly reverse sorted
trace Linear.java array=2,4,6,8,0,9,7,5,3,1 seek=5
check Linear.java
check Insertion.java sorted
check Insertion.java displacedpc=1

where the first argument after the command name is the name of your source file.

You are recommended to keep the JAVA filenames of the exercises as they are given, but you may, if you wish, copy the templates to files with different names, for example if you want to try a different way of doing things. In this case you also have to change the name of the class that the file defines. Then you can simply run the TESTER using the new filename.

5 Running your method once using the TESTER

To run the TESTER on the first exercise (linear search), type

   run Linear.java

to which the response will be something like this:

   Recompiling your class file ...
   Using /homes/pt/DCS127/tester.jar
   QMW/DCS/127 "Intro to Algorithms" Tester, (v2: 2001.03.29)
   <pt@turing> Java v1.2.2 11:13 Fri  2 Nov 2001.
   Problem: Searching unsorted data; Experiment: run with multiple threads; 
   Source: Linear.java; Last modified: 13:13 Sat  3 Feb 2001.
   Your method was asked to search for 11 in the following array:
   # 18 13 12 12 12 10 18  8  0  0  7  8 10 16  5 16  5  4 17  5  9# 
   The position returned was -1, which is outside the array,
   the required value being absent.

The hash character (#) is placed in the printout of the array to the left of the position that was returned by your method. If the value is not present, or if your method alters the array, returns an incorrect result, fails to terminate or throws an exception, then this is reported.

If you do this again you will get another random array of length 20.

You can specify the size (length) of the array, the range (magnitude) of the numbers that it is to contain, or that they are to be sorted (in ascending order), as follows:

   run Linear.java size=100 range=50 sorted

However, if the array is too big for the width of your screen then it will not be printed out in the report.

You can instead specify the actual numbers to be used in the array, and the value to be found:

   run Linear.java array=3,5,7,9,0,8,6,4,2,1 seek=4

Beware that no spaces are allowed in the array specification.

6 Debugging and tracing

If you are having difficulty with getting your method to work, you can make it print out messages by including lines like

    Trace.println("position=" + position + ", contains " + array[position]);

in the code. Do not use System.out.print to do this. Trace.println() does the same thing, but it is silent unless the trace keyword is used:

   trace Linear.java

This means that, when you come to do time-complexity testing (which runs your method thousands or even millions of times), the resulting spew of output will be suppressed.

(In general, you should never delete debug lines like this from your source code. When you have finished with them, either comment them out (i.e. put // in front of them) or - better - make them switchable by writing things like

   if (verbose > 3) { Trace.println (''position='' + position); }

so that you can use the debugging lines again later by setting verbose to an appropriate value.)

You can watch the progress of the algorithm on the array by calling the method

   Trace.printarray (array, i, j, k);

whose arguments are the array and up to five pointers. This prints output similar to that shown in the simple report above.

7 Thorough correctness testing

When you are satisfied with the way that your method works, you can subject it to much more thorough testing by typing

   check Linear.java

\Tester will then make a more general report on the behaviour of your method, such as

   For values that are actually PRESENT in the array, your method finds the
LEFTMOST occurrence.  For ABSENT values, it returns -1.

This is not an alternative to your own testing. The report is deliberately not specific enough to tell you how to modify your code to make it work: in real life program bugs manifest themselves in far more obscure ways than this. You must do single runs, as in the previous section, to debug your code.

8 Timing and time-complexity testing

If the \Tester considers that your algorithm is reasonably close to being correct, it will run it several thousand times on arrays of varying sizes, and tell you how long this took:

    size      time (seconds)    repetitions
      30      o.ooo 112 5           10814
      40      o.ooo 110 6           10000
      50      o.ooo 112 6            9445
     ...      ...                     ...
   70000      o.oo3 778              1094
   80000      o.oo4 295              1074
   90000      o.oo4 718              1056
  100000      o.oo5 19                180
Your method has LINEAR time complexity, within 5%:
for size n it takes 50 + 0.0535 * n microseconds.
To see the graph, please type
     gnuplot Insertion.plot
This is a PLAIN TEXT file: LOOK AT IT to see how to send the graph to 
the printer.

It takes considerably longer than the time shown to do this test, because (in order to achieve some experimental accuracy and reliability) your method is called thousands of times. The timing shown is for each call.

When several timings have been made, \Tester attempts to fit a straight line or some other function to the graph of timings. The percentage at the end shows how successful that was: 2% is good, 9% is bad and any more than that is reported as failure.

The TESTER then draws a graph to show both the individual timings and the best-fitting curve through them. To see this do

    gnuplot Linear.plot

(or whatever filename the TESTER tells you). This file is plain text and contains commands in the gnuplot plotting language. Read it for instructions on how to send the plot to the printer.

You can run the test for another sequence of sizes like this:

   check Linear.java size=10000 by=10000 to=100000

This will give the arithmetic progression 10000, 20000, 30000, ..., except in the case of Binary search, where by multiplied instead, so

   check Binary.java size=1 by=2 to=1000000

gives the geometric progression 1, 2, 4, 8, 16, ..., 1048576.

As with the single runs, you can use sorted arrays and state the range of numbers that they contain, but specifying the actual contents of the array or the value to seek has no effect.

The TESTER may find that the times reported are too erratic to fit the appropriate function to them. Unfortunately, linear search is the most unreliable algorithm in the course from this point of view! This is because the entire program and array is loaded into the CPU cache and executed very fast, without accessing RAM at all - usually. Occasionally, however, this process is interrupted by something else, and ends up taking much much longer.

You should shut down Netscape before trying to do these timing experiments, because (even when you're not looking at any Web pages) from time to time it takes up memory and CPU time with its activities. The Gnome window manager is another culprit: it is Similarly, if you are competing with the other students for CPU time on the communal machines (bronwyn or linus) then your timing will be less reliable than on a machine that you alone are using.

The printout of timings in the TESTER was designed to emphasise that you have at best three digits of precision, because the JAVA system clock only measures milliseconds, and may not do that very well. This does not, however, seem to be an important factor in how well curves can be fitted to the experimental data.

9 Summary of TESTER command-line arguments

For single runs, the TESTER provides a random unsorted array that can be printed across your screen, containing values from 0 to the size. So on average each value in this range occurs once.

The various problems that the TESTER encodes may set different default values, and the comprehensive correctness tests largely set their own parameters.

The timings are done with arrays of various sizes, so some of the options below set parameters in ways that depend on the size.

Many of the options are applicable only to certain problems, or to certain algorithms.

In fact, the arguments are passed using the normal Unix/ JAVA mechanism, being separated by spaces. It does not matter in what order you write them. An argument is either a single keyword, or a keyword=value pair. If the value contains special characters such as space or *()[]<>?|$!& then you must put (single) quote characters around the argument.

The following command line parameters are used, with examples:

array=1,3,5,7,9,0,8,6,4,2: use exactly this array (be careful not to include space characters in the string).
choice=3: the TESTER calls choice(3) in your class (this allows you to put several attempts or versions in the same class file, as the cases of a switch, as for example in the exercise on binary search).
convex=true: make a sawtooth like 0,1,2,3,2,1,0 instead of 3,2,1,0,1,2,3 (for quicksort).
cutoff=25: call cutoff(25) in your class (for hybrid mergesort and quicksort).
debug: verbose output for me to debug the TESTER.
density=2.0: use range=size/2, so each value occurs on average twice.
dest=5: call shift (array, source, 5, len) (for shift).
displaced=5: scatter 5 random values in a sorted array (for insertion and bubble sort).
displacedpc=1: scatter 1% of random values in a sorted array.
easy=true: give the shift method easy arguments (for shift).
fit=linear: accept linear complexity and generate the graph, however bad the experimental results are (similarly logarithmic, quadratic, nlogn and power).
help: print a help text.
largesizes use a sequence of array sizes from 8192 to 262144.
len=5: call shift (array, source, dest, 5) (for shift).
'markers=[]/': use these characters instead of # in Trace.printarray (be careful to enclose this in quotes to protect it from interpretation by the operating system).
maxtime=60: how long the TESTER should wait before concluding that your method is not going to terminate.
plot=file.plot: the name of the file in which to write gnuplot commands to draw a graph.
quiet: reduce the output, in particular don't print out all the timings.
range=100: how big the random numbers should be.
range_lower=10: random numbers to be at least 10.
range_upper=100: random numbers to be less than 100.
restmore=true: the numbers in the unsorted segment after upto are to be greater than those in the sorted segment before this point (for LocatingMinimum for selection sort).
reverse=true: sorted in descending order.
sawtooth=2: sawtooth pattern like 6,3,1,2,3,4,5 that starts with a descending sequence of 2 numbers (for quicksort).
sawtooth=−2: sawtooth pattern like 5,4,3,2,1,3,6 that ends with an ascending sequence of 2 numbers.
sawtoothpc=50: sawtooth pattern with its vertex at 50% of size.
screenwidth=80: this controls line-breaking of text messages and the default array size, and is set in the run perl script.
seek=5: call search (array, 5) or where_to_insert(array, upto, 5) (for linear and binary search).
showfit: print information about curve fitting for me to debug the TESTER.
size=15: use an array of size 15 for a single run.
sizes=30, 40, 50, 60, 70, 80, 100, 120, 140, 160, 180, 200, 220, 250, 300, 400, 500, 600, 700, 800, 1000, 1200, 1500, 2000, 2500, 3000, 4000, 5000, 6000, 7000, 8000, 10000, 12000, 15000, 20000, 25000, 30000, 35000, 40000, 50000, 60000, 70000, 80000, 90000, 100000: use these sizes for timing (this list is the default, in case you want to cut and paste part of it).
smallsizes use a sequence of array sizes from 256 to 8192 (for binary search).
sorted=true: generate sorted arrays.
source=5: call shift (array, 5, dest, len) (for shift).
strictly: generate sorted arrays without repetitions.
thread=true: use threads to catch non-terminating processes and for timing.
upto=5: call where_to_insert(array, 5, seek) or where_is_min (array, 5).

10 Running the TESTER without the perl script

If you are working with Linux in the ITL, you will find that TESTER and the run, trace and check commands for using it have been set up for you already in your work directory (DCS127). You do not need to do anything to install them.

The TESTER itself will be updated as the course progresses, as each exercise that you do needs me to write additional testing code. So long as you leave the commands in your work directory as they are, you will get the new versions automatically.

The TESTER may be able to work with Windows NT, but I haven't tried it. The timing experiments have been calibrated to work under Linux on the student workstations on the ground floor of the ITL: the timings may work on other machines, but this is not guaranteed.

In order to take the TESTER home you will need both the JAVA Archive file tester.jar containing the TESTER itself and the perl script for the run, trace and check commands. This single file, called run, can do "run", "trace" OR "check" - which of the three it does depends on the name by which you call it. So install it as run and then do

    chmod +x run
    ln -s run trace
    ln -s run check

to make it executable and create symbolic links (aliases) for it.

You can use the TESTER without using this perl script at all (for example if you only have Microsoft Windows at home), but this is more complicated.

Assuming that "tester.jar" is in the current directory, to compile your class (say, Insertion.java) you have to do

    javac -classpath tester.jar Insertion.java

and then to perform a single run you do

    java -cp .:tester.jar Tester Insertion.java

or with tracing,

    java -cp .:tester.jar Tester Insertion.java trace

and to do the comprehensive correctness and timing test, do

    java -cp .:tester.jar Tester Insertion.java test
    java -cp .:tester.jar Tester Insertion.java time

You can add other options to the end of the command line in the same way as you would using this script under Linux in the ITL.

If your code throws an Exception, you can get a more informative indication of where it happened than "Compiled code" by doing

    java -Djava.compiler=NONE -cp .:tester.jar Tester Insertion.java

Since this runs the JAVA run-time interpreter (instead of compiling the JAVA class file into machine code immediately before running it), your code will run more slowly. This doesn't matter, since we're learning about the functions (linear, logarithmic, quadratic, nlog(n), etc.). It's just that you can't compare timings made using the interpreter with those made using the compiler.

The classpath argument connects your code to the TESTER, whilst NONE makes the JAVA run-time system use the interpreter, as a result of which you get line numbers (instead of "Compiled code") in the stack trace when an exception occurs. By default, JAVA 1.2 uses a "just-in-time" compiler, i.e. it translates the (machine-independent) class file into machine code immediately before running it.

This is www.PaulTaylor.EU/algorithms/tester.html and it was derived from algorithms/tester.tex which was last modified on 21 July 2007.