Algorithm is a schematic procedure, which consists of a finite number of steps and solves certain type of problem. However this term is mainly used in computer science, its usage is much wider (recipes, manuals and instructions...). The word algorithm itself stems from the name of a Persian mathematician of 9. century Abu Jafar Muhammad ibn Mūsā al-Chwārizmī, who had in his work laid the foundations of algebra (Arabic numerals, solutions to the linear and quadratic equations).

Properties of algorithms

• Finiteness – Algorithm terminates after a finite number of steps.
• Definiteness – All steps of the algorithm are precisely defined.
• Correctness – Algorithm returns for any correct input a correct output in finite number of steps.
• Generality – Algorithm solves all problems of a certain type.

Classification of algorithms

Iterative and recursive algorithms

An iterative algorithm is based on a repetition of a set of instructions (block) using a loop construct of the programming language. A recursive algorithm repeats the code by calling itself. Every recursive algorithm can be translated into its iterative form, which is often done automatically by the compiler (or virtual machine) of the programming language.

The main advantage of recursive algorithms is their compactness and understandability. Their disadvantage is a need of additional system resources to maintain the call stack.

• Iterative – bubble sort, insertion sort
• Recursive – merge sort, quicksort

Deterministic and non-deterministic algorithms

An algorithm is deterministic, if it has in every step only one choice, how to progress. On the contrary non-deterministic algorithm has more possible choices. As an example can serve the deterministic and the non-deterministic finite automaton.

Serial, parallel and distributed algorithms

Serial algorithm performs all its steps one by one, parallel algorithm perform more steps at the same time, distributed algorithm performs more steps at the same time on different machines.

Asymptotic complexity

Asymptotic complexity states, how many operations must the algorithm perform to generate its output (multiplicative and additive constants are omitted). If we search the array of a size using linear search (we inspect each element), we know, that we will find the element in at most steps. If we sort the array using bubble sort, the algorithm will perform at most steps.

Complexity class

Hierarchy of complexity classes

The complexity class is determined by the type of a Turing machine, which can implement the algorithm.

• Complexity class P – consists of problems, which can be decided in polynomial time by a deterministic Turing machine.

  • Contains the given graph a spanning tree of a size at most ?
  • Exists in the given acyclic graph simple path between nodes a and b, whose length is at most ?
• Complexity class NP – consists of problems, which can be decided in polynomial time by a non-deterministic Turing machine.

  • Travelling salesman problem.
  • Is there a Hamiltonian circuit in the given graph?
  • Can be the graph colored using at most colors?

Sources

• WRÓBLEWSKI, Piotr. Algoritmy : Datové struktury a programovací techniky. Brno : Computer press, 2004. 351 p. ISBN 80-251-0343-9.
• KVASIL, Bohumil, et al. Algoritmus. In Malá československá encyklopedie. Praha : Academia, 1984. p. 108.
• VELEBIL, Jiří. Diskrétní matematika : Text k přednášce. Praha : [s.n.], 2007. 197 p.