What is an "algorithm"?

[Stefan Ram]

An algorithm can be either hidden or exposed.

A hidden algorithm is part of every function, for example,
»::std::fopen« internally uses some kind of algorithm to
open a file.

So, one might think that the difference of the entries in
<algorithm> was that these were exposed algorithms. But no,
AFAIK the specific algorithm used is not exposed, for
example, we do not know AFAIK the specific sort algorithm
(is it quicksort, mergesort, heapsort, bubble sort, or
what?) used in »::std::sort« (we only know something about
its complexity).

So, then, why is »::std::sort« called an »algorithm« and
»::std::fopen« is not?

 

[Alf P. Steinbach]

An algorithm can be either hidden or exposed.

A hidden algorithm is part of every function, for example,
»::std::fopen« internally uses some kind of algorithm to
open a file.

So, one might think that the difference of the entries in
<algorithm> was that these were exposed algorithms. But no,
AFAIK the specific algorithm used is not exposed, for
example, we do not know AFAIK the specific sort algorithm
(is it quicksort, mergesort, heapsort, bubble sort, or
what?) used in »::std::sort« (we only know something about
its complexity).

So, then, why is »::std::sort« called an »algorithm« and
»::std::fopen« is not?

The terminology stems from Stepanov and Musser's work on the STL, where
a main idea was to separate algorithms from data structures, so that to
a large degree just about any algorithm could be applied to just about
any data structure.

That is, these are /generic algorithms/.

std::sort, a generic algorithm, can be applied to any data structure
that provides the requisite iterators, while ::fopen can only be applied
with fixed type arguments.

* * *

For the more abstract Computer Science definition of algorithm I like
Donald Knuth's old one, where a main characteristic is that an algorithm
is guaranteed to /terminate/. So with that definition an continuous
process isn't an algorithm, no matter how algorythmic it is. I like that
because it shows how even the most abstract definitions can have hidden
dependencies on technology. Let me not at all mention also Knuth's
definition of "reel time". I think /that/ was just a joke... ;-)


Cheers & hth.,

- Alf