[comp.software-eng] Implementing algorithms

sommar@enea.se (Erland Sommarskog) (05/13/88)

James T Krist (jtkrist@ihlpf.UUCP) writes:
>golly, this could be me! whenever i need to implement an algorith, i
>look first in knuth and if i find what i need, i transliterate the
>algorithm, as closely as possible, in the language i'm using - yes i
>know it's not structured and there are lots of labels and gotos, but
>it works - who was it who said that scientists stand on each other's
>shoulders, while programmers stand on each other's toes?

Well, as long as the given algorithm is complete. Our technical 
director asked me to implement in Ada the algorithm for topological 
sorting given by Knuth. Not for any particular application, but  
rather as a reference. He had himself a few years back implemented 
the algorithm in C.

(The problem for you who are unacquinted with it: Given a number
of objects and a number of depenecies bewteen them. E.g. A depends
on B and E, B and C depends on F, etc. Order them so that an object 
follows the objects it depends on. A typical application is make(1).)

In his book Knuth simply assumes that the objects are numbers from
1 to N. (He has N objects.) This is a simple case, since we just 
can store them in an array. If we want to write a general reusable 
package, this won't do. We must have a method to see: have we had 
this object before or not? Knuth does not discuss this problem here, 
so we have to think for ourselves. (Our look elsewhere in the book.) 
  In the old C program he used a hash table, assuming that whatever
input data really was, it had been casted to character pointers.
  I preferred a binary tree which is probably slower, but I wanted
to save the user of the package from providing me a hash function.
(But he has to give me an assignment procedure and possibly also 
comparison operators ("<" and ">").
  Besides the very simplified user interface, Knuth's implementation
contains some other tricks. Particulary, for each object he is  
using the same memory cell for two different meanings. First as a
counter and then as a link in a queue output objects. Saves memory,
but is an example of obscure programming.

Note: tsort(1) provides topological sorting, but uses another algorithm,
that is quadratic with respect to number of objects. Knuth's algorithm 
is linear.

----------------------------------------------------------------------

If you care to listen, here's another story. Problem: Given a polygon
as a suite of points and a rectangular reference area (viewport). Clip 
the polygon so that the remaining polygon(s) are entirely inside (alt. 
outside) the viewport.
  I was working with implementing a GKS-like package, so this problem
naturally came in our way. Since we were not the first ones to implement
GKS, the problem must have been solved before. So what did we do? Did
we just pick up the right book and copied it right off? Well, in a way,
we did. In a way, we did not.
  A collegue of mine rewrote an old program using a book algorithm. However,
if the polygon was split in two or more, this algorithm retained lines 
along the viewport edges connecting the pieces. He added an algorithm 
for removing these lines. Not a trivial problem.
  Myself, I started thinking from scratch and came up with a different
algorithm, which was "clip and combine" instead of "clip and split". 
It didn't take me to much time to figure it out. Implementation took 
a little longer. Going searching for the right book - and waiting for 
its arrival - would probably have the same time, and would have been 
less fun.

-- 
Erland Sommarskog           Take C, a third class language 
ENEA Data, Stockholm        and a C programmer, i.e. a third class programmer
sommar@enea.UUCP            => A ninth class program, a C program.

EGNILGES@pucc.Princeton.EDU (Ed Nilges) (05/16/88)

In article <3278@enea.se>, sommar@enea.se (Erland Sommarskog) writes:
 
>Knuth does not discuss this problem here,
>so we have to think for ourselves.
 
Nothing wrong with that!  The reason for using algorithms in books (or
canned software) is not to prevent thinking, but to build a better
product, and give the maintenance programmer a resource.
 
I typically have to manually translate Knuth's algorithms into a
structured style. This is not a waste of time, since I understand
the algorithm if I have structured it.