Re: What is an "algorithm"?

[Alf P. Steinbach]

On 15.11.2013 17:48, Stefan Ram wrote:
> 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