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

2  Disclaimers

3  Objectives

The TESTER  Later versions of the TESTER will

4  Using the TESTER

The TESTER can 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 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:

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.