====================

 The nitty gritty of running the algorithms from 
 Programming Pearls, column 8 : "Algorithm Design Techniques"
 and seeing the O() behavior graphically.

====================

Here's how I got the source :

 $ wget http://netlib.bell-labs.com/cm/cs/pearls/maxsum.c
 $ cp maxsum.c maxsum.c.orig
 $ fixcrlf maxsum.c; rm maxsum.c.orig

Then I edited mascum.c a bit and compiled it with

 $ make maxsum
 cc -march=pentium4 -O3    maxsum.c   -o maxsum

To see the differences between these two versions,
 $ diff maxsum.c maxsum.c.orig > maxsum.diff
or
 $ diff --side-by-side --minimal \
   maxsum.c maxsum.c.orig > maxsum_side-by-side.diff
(The unix "diff" utility can be useful for making "patches" which
 can be applied to files to make small changes.  See "man diff"
 and "man patch".)

After a bit of playing around to see what was needed,
I then created various input files for testing the different algorithms.

For example, this one tests the slowest algorithm, algorithm 1 :

 --- maxsum1.in ------
 1      1000
 1      2000
 1      3000
 -1 -1
 ---------------------

where the numbers are 

 algorithm  n

and "-1 -1" means "exit.

A sample output file is

 --- maxsum1.out --------------------------------
 1	1000	15.617510	260000	0.260000
 1	2000	26.738892	2120000	2.120000
 1	3000	25.277367	7120000	7.120000
 ------------------------------------------------

where the numbers are 

 alg    n       answer          ticks   time_in_sec

which means that with n=3000 (3000 numbers in the array),
algorithm 1 takes 7.12 seconds to run.

The file "run" runs all the inputs, creates the outputs,
and invokes gnuplot to create the plot, using the 
commands in "plot.pg".  It looks like this :

 --- run ----------------------------
 ./maxsum < maxsum1.in > maxsum1.out
 ./maxsum < maxsum2.in > maxsum2.out
 ./maxsum < maxsum3.in > maxsum3.out
 ./maxsum < maxsum4.in > maxsum4.out
 gnuplot plot.gp
 -------------------------------------

The input to gnuplot looks like this.
(Google "man gnuplot" for more details.)

 --- plot.gp -----------------------------------------------
 set terminal png color
 set logscale xy
 set xlabel "n"
 set xrange [1e2:1e8]
 set yrange [5e-3:1e1]
 set ylabel "sec"
 set output "plot.png"
 plot "maxsum1.out" using 2:5 with linespoints linetype 1, \
      "maxsum2.out" using 2:5 with linespoints linetype 8, \
      "maxsum3.out" using 2:5 with linespoints linetype 29, \
      "maxsum4.out" using 2:5 with linespoints linetype 24
 -------------------------------------------------------------

The "2:5" means "x is column 2, y is column 5"
and the "linetype" refers to the colors in test.png,
which was created with
 $ gnuplot
 $ set terminal png color
 $ set output "test.png"
 $ test

Finally, with all this infrastructure set up, the whole thing
is run with

 $ time ./run

or just
 
 $ ./run

To run these things in the background if they get big and slow
you may want to use the unix "batch" command; see "man batch" for details.

The picture you get after all this is plot.png.

So there you are.

 Jim Mahoney
 March 2006