0.2 Introduction to algorithms  (Page 2/8)

Representations of algorithms are generally classed into three accepted levels of Turing machine description (Sipser 2006:157):

• 1 High-level description:

"...prose to describe an algorithm, ignoring the implementation details. At this level we do not need to mention how the machine manages its tape or head"

• 2 Implementation description:

"...prose used to define the way the Turing machine uses its head and the way that it stores data on its tape. At this level we do not give details of states or transition function"

• 3 Formal description:

Most detailed, "lowest level", gives the Turing machine's "state table".

As it happens, it is important to know how much of a particular resource (such as time or storage) is required for a given algorithm. Methods have been developed for the analysis of algorithms to obtain such quantitative answers; for example, the algorithm above has a time requirement of O(n), using the big O notation with n as the length of the list. At all times the algorithm only needs to remember two values: the largest number found so far, and its current position in the input list. Therefore it is said to have a space requirement of O(1). (Note that the size of the inputs is not counted as space used by the algorithm.)

Different algorithms may complete the same task with a different set of instructions in less or more time, space, or effort than others. For example, given two different recipes for making potato salad, one may have peel the potato before boil the potato while the other presents the steps in the reverse order, yet they both call for these steps to be repeated for all potatoes and end when the potato salad is ready to be eaten.

The analysis and study of algorithms is a discipline of computer science , and is often practiced abstractly without the use of a specific programming language or implementation. In this sense, algorithm analysis resembles other mathematical disciplines in that it focuses on the underlying properties of the algorithm and not on the specifics of any particular implementation. Usually pseudocode is used for analysis as it is the simplest and most general representation.

There are various ways to classify algorithms, each with its own merits.

Classification by implementation

One way to classify algorithms is by implementation means.

• Recursion or iteration: A recursive algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition matches, which is a method common to functional programming . Iterative algorithms use repetitive constructs like loops and sometimes additional data structures like stacks to solve the given problems. Some problems are naturally suited for one implementation or the other. For example, towers of hanoi is well understood in recursive implementation. Every recursive version has an equivalent (but possibly more or less complex) iterative version, and vice versa.

• Logical: An algorithm may be viewed as controlled logical deduction . This notion may be expressed as:

Algorithm = logic + control.