What is an "algorithm"?

S

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?
 
A

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top