One kind of algorithms which even non-geeks use regularly, and which is amazingly popular on Everything is cooking recipes. In cuisine as in programming, good implementation of the outlined procedures can be just as challenging and creative as the abstract work, and can fail or succeed spectacularly.

"Cryptography is a black art; if you don't know what you're doing, you can easily get into trouble."

- Bruce Schneier: Applied Cryptography, 2nd ed.

Algorithms are, as told above, "blueprints" of how specific computing tasks should be done.

There are many different sorts of algorithms for many tasks, some better suited for some tasks, some for others. Good rules to remember:

  1. Don't pick them from your hat. Choose well.
  2. Don't make shit up. Someone who had IQ way, way, way above yours invented a better one, so use that instead. (And there's nothing to be ashamed of about that! The details of implementation are what really matter. Picking the correct course of action is a form of art, too!)

During the "Data Structures and Algorithms" course last year, the lecturer told a common story about students who tried to make the required assignment: People made up their own algorithms, ended up doing things that were of exponential complexity, and spent hours and hours trying to make the correct implementation. People who picked up an algorithm shown on lectures and made their assignment based on that information made highly efficient programs very quickly and lived happily ever after.

Consider this one, for example: Bubble sort is O(n²) in worst case - sorting 100 items takes 100² = 10000 units of time. Quick sort (that they called the "sign of academic background") is O(n log n) on average - sorting 100 items takes 460.52 units of time. For 1*106 items, the times are 1*1012 and 1.3816*107. Clearly some improvement...

Most beginners will only make fancy versions of bubble sort, so knowing the quick sort algorithm will help a lot. Indeed, if you try to make a better algorithm when you only know how bubble sort works, you may end up creating an algorithm that's even worse than bubble sort.

To illustrate the importance of picking the correct algorithm, let me say that quick sort performs badly on almost-ordered data, but bubble sort is very fast in that case.

And the Schneier quote above tells a lot about the importance: If you try to make your own encryption algorithm, you may end up making a very insecure algorithm. To repeat: Don't think you're too smart when the smart guys have already made really cool algorithms. =)

Webster is definitely outdated on this, the word is in a different category today: we don't use 'algorithm' as a mass noun. An algorithm is a concrete recipe for execution. It is not limited to calculation. So we need a better definition.

An algorithm is a specific combination of discrete steps, observations or actions, into a complex method. It is described in terms of elementary entities, objects, properties, actions, processes and events. The algorithm itself consists of the way in which these are combined into a whole method. The execution of an algorithm is the sequence of actions resulting from applying the algorithm - the result varies depending on the circumstances, which may lead to different outcomes.

A familiar kind of algorithm is the cookbook recipe. Elementary entities (ingredients and tools), observations ('a teaspoonful', '300 g', 'boiling', 'fully dissolved'), actions ('chop into small pieces', 'mix', 'bring to the boil'), processes ('melt', 'boil') and events (in cooking, always time having elapsed, or changes of state of the food being prepared) are the elements; the recipe is the algorithm describing how to combine them in order to create a specific dish.

This also applies to computer algorithms, except that they don't work with food, they work with what is available in a computer. A computer program is a concrete implementation of one or more algorithms.

Note that when using the term in this very general sense, algorithms can work with basically anything, not just numbers, and they aren't necessarily stepwise processes executed one by one by a single processor: they may include continuous processes, external, unpredictable events, and nondeterministic, concurrent, or distributed actions. A specific type of activity is calculation, in which all activity is : it is stepwise, the steps being executed one after the other by a single processor; the problem domain is described in terms of a complex, but discrete state, the kind that can be represented on a computer, for instance, lists of numbers; all observations are tests of state, all actions are changes of state, and no external state changes occur during the algorithm's execution. Such algorithms of calculation are the type usually discussed in theoretical computing science, which has an extensive theory on the properties of such algorithms and the relationships between them. A calculation is the result of the execution of such an algorithm.

A nondeterministic algorithm does not uniquely determine the course of action at every point, but leaves a choice between a set of options. We usually think of algorithms as deterministic, but this particular notion is important in the theoretical study of algorithms, summarised in the question, still open in theory, whether or not P = NP.

Calculation is often numerical, and the classical algorithmics of algebra, of addition, subtraction, multiplication and division, are greatly emphasized in school. Some well-known numerical algorithms, such as Euclid's algorithm to detemine the greatest common divisor, are known from ancient times.

Now that computers are everywhere, algorithms in different types of data become more important: searching and transformations on text strings, image manipulation algorithms on vector-based or bitmapped images, manipulations on databases, document structures, or other forms of structured data.

Part of the art of algorithm design is good use of complex data structures. Different representations of data typically have different efficiency characteristics. For instance, lists of items can be stored in an array, linked list, or hash table, each with different average cost in time and space for various typical access and update operations..

dido makes the interesting point that an algorithm is supposed to terminate on all input -- in other words, it must express a computable function. The main reason I find this interesting is that I do not consider this requirement to be part of what an algorithm is, while dido does. For example, for me the famous Collatz sequence describes an algorithm, while dido cannot tell. Some Googling demonstrates that, like dido and me, dictionaries of computing science disagree on this matter. So I will just leave you with a reminder to carefully examine whether the definition of "algorithm" you encounter assumes guaranteed termination or not.

From m-w.com: an algorithm is: broadly, a step-by-step procedure for solving a problem or accomplishing some end especially by a computer

The theory of algorithms deals with the study of characteristics of algorithms such as efficiency in terms of time and space.


Al"go*rism (#), Al"go*rithm (#), n. [OE. algorism, algrim, augrim, OF. algorisme, F. algorithme (cf. Sp. algoritmo, OSp. alguarismo, LL. algorismus), fr. the Ar. al-Khowarezmi of Khowarezm, the modern Khiwa, surname of Abu Ja'far Mohammed ben Musa, author of a work on arithmetic early in the 9th century, which was translated into Latin, such books bearing the name algorismus. The spelling with th is due to a supposed connection with Gr. number.]

1.

The art of calculating by nine figures and zero.

2.

The art of calculating with any species of notation; as, the algorithms of fractions, proportions, surds, etc.

 

© Webster 1913.

Log in or register to write something here or to contact authors.