What is an Algorithm?
Before we start talking about algorithms, we should try to figure out what an algorithm actually is. We could, for example, have a short look at how others define an algorithm:
Several definitions found in the WWW:
Browsing the web, we can find quite a number definitions of the term "algorithm". Here's a small collection of them.
"An algorithm is a computable set of steps to achieve a desired result." - (found on numerous websites)
An algorithm is a set of rules that specify the order and kind of arithmetic operations that are used on specified set of data.
An algorithm is a sequence of finite number of steps arranged in a specific logical order which, when executed, will produce a correct solution for a specific problem. - (taken from an undergraduate course at UMBC).
An algorithm is a set of instructions for solving a problem. When the instructions are followed, it must eventually stop with an answer. - (given by Prof. Carol Wolf in a course on algorithms).
An algorithm is a finite, definite, effective procedure, with some output. - (given by Donald Knuth)
Essential properties of an algorithm
Though the given definitions differ slightly, we can clearly extract the essential properties an algorithm should have:
* an algorithm is finite (w.r.t.: set of instructions, use of resources, time of computation)
- * instructions are precise and computable.
- * instructions have a specified logical order, however, we can discriminate between
- - - deterministic algorithms (every step has a well-defined successor), and
- - - non-deterministic algorithms (randomized algorithms, but also parallel algorithms!) * produce a result.
Basic questions about algorithms:
For each algorithm, especially a new one, we should ask the following basic questions:
- * does it terminate?
* is it correct?
* is the result of the algorithm determined?
* how much memory will it use?