User Tools

Site Tools


cs101:algorithms

Algorithms

Knuth's 5 Characteristics

(from scriptol):

Knuth (1968, 1973) has given a list of five properties that are widely accepted as requirements for an algorithm:

Finiteness: “An algorithm must always terminate after a finite number of steps”
Definiteness: “Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case”
Input: “…quantities which are given to it initially before the algorithm begins. These inputs are taken from specified sets of objects”
Output: “…quantities which have a specified relation to the inputs”
Effectiveness: “… all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil”

Knuth offers as an example the Euclidean algorithm for determining the greatest common divisor of two natural numbers.
Articles on Specific Algorithms
cs101/algorithms.txt · Last modified: 2013/07/23 23:08 by scarl