# Algorithm

Algorithm (from the name of Persian mathematician Muhammad ibn Musa al-Khwarizmi) is an exact step-by-step description of how to solve some type of a problem. Algorithms are basically what programming is all about: we tell computers, in very exact ways (with programming languages), how to solve problems -- we write algorithms. But algorithms don't have to be just computer programs, they are any kind of exact description for how to solve specific types of problems. Although it may not be immediately evident, mathematics similarly revolves around algorithms because it works towards giving us exact instructions for solving problems -- a mathematical formula usually tells us (not explicitly but in an implied way) what we have to do to calculate a result, so in a way it is a sort of algorithm too. A "series of steps" is a good enough definition of algorithm for everyday use, however for computer scientists there is a much more precise, mathematical definition, which states that algorithm is that which can be represented by a Turing machine.

Cooking recipes are commonly given as an example of a non-computer algorithm, though they rarely contain branching ("if condition holds then do...") and loops ("while a condition holds do ..."), the key features of algorithms. The so called wall-follower is a simple algorithm to get out of any maze which doesn't have any disconnected walls: you just pick either a left-hand or right-hand wall and then keep following it. Long division of numbers which students are taught at school is also an algorithm. You may write a crazy algorithm basically for any kind of problem, e.g. for how to clean a room or how to get a girl to bed, but it has to be **precise** so that anyone can execute the algorithm just by blindly following the steps; if there is any ambiguity, it is not considered an algorithm; a vague, imprecise "hint" on how to find a solution (e.g. "the airport is somewhere in this general direction.") we rather call a heuristic. Heuristics are useful too and they may be utilized by an algorithm, e.g. to find a precise solution faster, but from programmer's point of view algorithms, the PRECISE ways of finding solutions, are the basics of everything.

Interesting fact: contrary to intuition there are problems that are mathematically proven to be unsolvable by any algorithm, see undecidability, but for most practically encountered problems we can write an algorithm (though for some problems even our best algorithms can be unusably slow).

Ordinarily (but not necessarily always) we write algorithms down as a **series of steps** (or "instructions"); these steps may be specific actions (such as adding two numbers or drawing a pixel to the screen) or **conditional jumps** to other steps ("if condition X holds then jump to step N, otherwise continue"). At the lowest level (machine code, assembly) computers cannot do anything more complex than that: execute simple instructions (expressed as 1s and 0s) and perform conditional jumps -- in this computers are quite dumb (their strength comes from being able to execute many instruction with extreme speed). These jumps can be used to create **branches** (in programming known as *if-then-else*) and **loops**. Branches and loops are together known as control structures -- they don't express a direct action but control which steps in the algorithm will follow. All in all, **any algorithm can be built just using these three basic constructs**:

- **sequence**: A series of steps, one after another. E.g. "write prompt, read number from input, multiply it by two, store it to memory".
- **selection** (branches, *if-then-else*): Two branches (blocks of instructions) preceded by a condition; the first branch is executed only if the condition holds, the second ("else") branch is executed only if the condition doesn't hold (e.g. "If user password is correct, log the user in, otherwise print out an error."). The second branch is optional (it may remain empty).
- **iteration** (loops, repetition): Sequence of steps that's repeated as long as certain condition holds (e.g. "As long as end of file is not reached, read and print out the next character from the file.").

Additional constructs may be introduced to facilitate programming further, e.g. subroutines/functions (kind of small subprograms which the main program may invoke), macros (shorthand commands that represent multiple commands) or switch statements (selection with more than two branches). Loops are also commonly divided into several types such as: counted loops, loops with condition and the beginning, loops with condition at the end and infinite loops (`for`, `while`, `do while` and `while (1)` in C, respectively) -- in theory there can only be one generic type of loop but for convenience programming languages normally offer different "templates" for commonly used loops. Similarly to mathematical equations, algorithms make use of variables, i.e. values which can change and which have a specific name (such as *x* or *myVariable*).

Practical programming is based on expressing algorithms via text in **programming languages**, but visual programming is also possible: flowcharts are a way of visually expressing algorithms, you have probably seen some. Decision trees are special cases of algorithms that have no loops, you have probably seen some too. Even though some languages (mostly educational such as Snap) are visual and similar to flow charts, it is not practical to create big algorithms in this way -- serious programs are written as a text in programming languages.

## Example

Let's write a simple algorithm that counts the number of divisors of given number *x* and checks if the number is prime along the way. (Note that we'll do it in a naive, educational way -- it can be done better). Let's start by writing the steps in plain English (sometimes called pseudocode):

1. Read the number *x* from the input.
2. Set the *divisor counter* to 0.
3. Set *currently checked number* to 1.
4. While *currently checked number* is lower or equal than *x*:
  - a: If *currently checked number* divides *x*, increase *divisor counter* by 1.
  - b: Increase *currently checked number*.
5. Write out the *divisor counter*.
6. If *divisor counter* is equal to 2, write out the number is a prime.

Notice that *x*, *divisor counter* and *currently checked number* are variables. Step 4 is a loop (iteration) and steps *a* and 6 are branches (selection). The flowchart of this algorithm is:

```
               START
                 |
                 V
               read x
                 |
                 V
       set divisor count to 0
                 |
                 V
       set checked number to 1
                 |
    .----------->|
    |            |
    |            V                no
    |    checked number <= x ? ------.
    |            |                   |
    |            | yes               |
    |            V                   |
    |     checked number    no       |
    |       divides x ? -------.     |
    |            |             |     |
    |            | yes         |     |
    |            V             |     |
    |     increase divisor     |     |
    |       count by 1         |     |
    |            |             |     |
    |            |             |     |
    |            |<------------'     |
    |            |                   |
    |            V                   |
    |     increase checked           V
    |       number by 1     print divisor count
    |            |                   |
    '------------'                   |
                                     V             no
                             divisor count = 2 ? -----.
                                     |                |
                                     | yes            |
                                     V                |
                           print "number is prime"    |
                                     |                |
                                     |<---------------'
                                     V
                                    END

```

This algorithm would be written in Python as:

```
x = int(input("enter a number: "))

divisors = 0

for i in range(1,x + 1):
  if x % i == 0: # i divides x?
    divisors = divisors + 1

print("divisors: " + str(divisors))
 
if divisors == 2:
  print("It is a prime!")
```

in JavaScript as:

```
function main()
{
  let x = parseInt(prompt("enter a number:"));
  let divisorCount = 0;

  for (let i = 1; i <= x; ++i)
    if (x % i == 0) // i divides x?
      divisorCount++;

  console.log("divisors: " + divisorCount);

  if (divisorCount == 2)
    console.log("It is a prime!");
}
```

in C as:

```
#include <stdio.h>
 
int main(void)
{
  int x, divisors = 0;

  printf("enter a number: ");
  scanf("%d",&x); // read a number

  for (int i = 1; i <= x; ++i)
    if (x % i == 0) // i divides x?
      divisors = divisors + 1;

  printf("number of divisors: %d\n",divisors);

  if (divisors == 2)
    puts("It is a prime!");

  return 0;
}
```

in Forth as:

```
variable x
variable divisorCount 

: main
  ." enter a number: "
  0     \ number to read

  begin \ read the number by digits
    key

    dup dup 48 >= swap 57 <= and
    while

    48 - swap 10 * +
  repeat
  drop

  dup . cr
  x !
  0 divisorCount !

  x @ 1+ 1 do
    x @ i mod 0 = if \ i divides x?
      1 divisorCount +!
    then
  loop

  ." number of divisors: " divisorCount @ . cr

  divisorCount @ 2 = if
    ." It is a prime!" cr
  then
;

main
bye
```

in comun as:

```
0
@@ # read X and convert to number
  <-
  $0 $0 "0" < >< "9" > | ? !@ .
  "0" - >< 10 * +
.
^

0 # divisor count
1 # checked number

@@
  $0 $3 > ?     # checked num. > x ?
    !@
  .

  $2 $1 % 0 = ? # checked num. divides x ?
    $1 ++ $:2   # increase divisor count
  .

  ++ # increase checked number
.

0 "divisors: " --> # write divisor count

$1 10 >= ?
  $1 10 / "0" + ->
.

$1 10 % "0" + -> 10 ->

$1 2 = ?
  0 "It is a prime" --> 10 ->
.
```

in Scheme Lisp as (here notice the difference in paradigm -- loop is replaced with recursion, as it's done in functional programming):

```
(define (countDivisors x countFrom currentCount) ; recursive function
  (if (> countFrom x)
    (begin
      (display "divisor count: ")
      (display currentCount)
      (newline)
      (if (= currentCount 2)
        (display "It is a prime!\n")))
    (countDivisors x (1+ countFrom)
      (+ currentCount (if (zero? (remainder x countFrom)) 1 0)))))

(display "enter a number: ")
(countDivisors (read) 1 0)
```

and also for fun in Brainfuck (a bit simplified version, made with our Macrofucker language):

```
[-]>[-]++++++++++++++++++++++++++++++++++++++++++++++++>,>[-]>[-]<<<[->>+>+<<<]
>>>[-<<<+>>>]<[-<->]<>[-]<[->+<]<[->+<]>>[-<<+>>]<[-]++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>[-]>
[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<>[-]<<-[->>>
[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<[-<+>]<<<]>>[-<<<+>>>]<<<>[-]+++++++++++++++
+++++++++++++++++++++++++++++++++>,>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<[-<->]<>
[-]<[->+<]<[->+<]>>[-<<+>>]<[-]++++++++++>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<>[
-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<>[-]<<-[->>>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>
]<[-<+>]<<<]>>[-<<<+>>>]<<<>[-]<[->+<]<[->+<]>>[-<<+>>]<<>[-]>[-]<<<[->>+>+<<<]
>>>[-<<<+>>>]<[-<+>]<>[-]++++++++++++++++++++++++++++++++++++++++++++++++>,>[-]
>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<[-<->]<>[-]<[->+<]<[->+<]>>[-<<+>>]<<>[-]>[-]<<
<[->>+>+<<<]>>>[-<<<+>>>]<[-<+>]<>[-]<[->+<]<<<[->>>+<<<]>>>>[-<<<<+>>>>]<<<<>[
-]>[-]<<[->+>+<<]>>[-<<+>>]<[>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<>[-]>[-]<<<[->
>+>+<<<]>>>[-<<<+>>>]<>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<<<[-]>>>[-]>[-]>[-]<<
<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<+<[->
->[-]>[-]<<[->+>+<<]>>[-<<+>>]<>[-]+<[[-]>-<]>[<+>[-]]<[<<<+>>>[-]]<<]<>[-]+<[[
-]>-<]>[<+>[-]]<[<<<+>>>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<[-<->]<>[-]>[-]>[-]<
<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<+<[-
>->[-]>[-]<<[->+>+<<]>>[-<<+>>]<>[-]+<[[-]>-<]>[<+>[-]]<[<<<+>>>[-]]<<]<>[-]+<[
[-]>-<]>[<+>[-]]<]<>[-]<[->+<]<[->+<]>>[-<<+>>]<<>[-]+<[[-]>-<]>[<+>[-]]<[<<<<+
>>>>[-]]<<-]<<>[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<>[-]
>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<<<[-]>>>[-]
>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>
>>>]<+<[->->[-]>[-]<<[->+>+<<]>>[-<<+>>]<>[-]+<[[-]>-<]>[<+>[-]]<[<<<+>>>[-]]<<
]<>[-]+<[[-]>-<]>[<+>[-]]<[<<<+>>>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<[-<->]<>[-
]>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+
>>>>]<+<[->->[-]>[-]<<[->+>+<<]>>[-<<+>>]<>[-]+<[[-]>-<]>[<+>[-]]<[<<<+>>>[-]]<
<]<>[-]+<[[-]>-<]>[<+>[-]]<]<>[-]<[->+<]<[->+<]>>[-<<+>>]<<>[-]<[->+<]<[->+<]>>
[-<<+>>]<>[-]++++++++++++++++++++++++++++++++++++++++++++++++>[-]>[-]<<<[->>+>+
<<<]>>>[-<<<+>>>]<[-<+>]<.<<<[-]++++++++++>>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<
>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<<<[-]>>>[-]>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<
<<<+>>>>]<>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<+<[->->[-]>[-]<<[->+>+<<]>>
[-<<+>>]<>[-]+<[[-]>-<]>[<+>[-]]<[<<<+>>>[-]]<<]<>[-]+<[[-]>-<]>[<+>[-]]<[<<<+>
>>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<[-<->]<>[-]>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-
<<<<+>>>>]<>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<+<[->->[-]>[-]<<[->+>+<<]>
>[-<<+>>]<>[-]+<[[-]>-<]>[<+>[-]]<[<<<+>>>[-]]<<]<>[-]+<[[-]>-<]>[<+>[-]]<]<>[-
]<[->+<]<[->+<]>>[-<<+>>]<<>[-]<[->+<]<[->+<]>>[-<<+>>]<>[-]+++++++++++++++++++
+++++++++++++++++++++++++++++>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<[-<+>]<.<>[-]<
[->+<]<[->+<]>>[-<<+>>]<>[-]++++++++++++++++++++++++++++++++++++++++++++++++>[-
]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<[-<+>]<.<<<<>[-]++++++++++.[-]++>[-]>[-]<<<[->
>+>+<<<]>>>[-<<<+>>>]<>[-]>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<[-<->]<>[-]+<[[-]>-<]
>[<+>[-]]<[[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++.[-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++.[-]++++++++++.[-]]
```

TODO: assembly, haskell, unix shell, ...

This algorithm is however not very efficient and could be **optimized** -- for example not only we wouldn't have to check if a number is divisible by 1 and itself (as every number is), but there is also no need to check divisors higher than the square root of the checked value (mathematically above square root there only remain divisors that are paired with the ones already found below the square root) so we could lower the number of the loop iterations and so make the algorithm finish faster. You may try to improve the algorithm this way as an exercise :-)

## Study of Algorithms

Algorithms are the center subject of computer science, there's plenty of theory and knowledge about them.

Turing machine, a kind of mathematical bare-minimum computer, created by Alan Turing, is the traditional formal tool for studying algorithms, though many other models of computation exist -- for example lambda calculus that's a basis of functional programming under which we already see algorithms in a bit different light: not as a series of steps but rather as evaluating mathematical functions. From theoretical computer science we know not all problems are computable, i.e. there are problems unsolvable by any algorithm (e.g. the halting problem). Computational complexity is a theoretical study of resource consumption by algorithms, i.e. how fast and memory efficient algorithms are (see e.g. P vs NP). Mathematical programming is concerned, besides others, with optimizing algorithms so that their time and/or space complexity is as low as possible which gives rise to algorithm design methods such as dynamic programming (practical optimization is a more pragmatic approach to making algorithms more efficient). Formal verification is a field that tries to mathematically (and sometimes automatically) prove correctness of algorithms (this is needed for critical software, e.g. in planes or medicine). Genetic programming and some other methods of artificial intelligence try to automatically create algorithms (*algorithms that create algorithms*). Quantum computing studies new kinds of algorithms running on quantum computers (a new type of still-in-research computers). Programming language design is the art and science of creating languages that express computer algorithms well. Etcetc.

## Specific Algorithms

Following are some well known algorithms.

- graphics
  - DDA: line drawing algorithm
  - discrete Fourier transform: extremely important algorithm expressing signals in terms of frequencies
  - Bresenham's algorithm: another line drawing algorithm
  - Midpoint algorithm: circle drawing algorithm
  - flood fill: algorithm for coloring continuous areas
  - FXAA
  - Hough transform: finds shapes in pictures
  - painter's algorithm
  - path tracing
  - ray tracing
  - ...
- math
  - Boot'h algorithm: algorithm for multiplication
  - Dijkstra's algorithm
  - Euclidean algorithm: computes greatest common divisor
  - numerical algorithms: approximate mathematical functions
  - sieve of Eratosthenes: computes prime numbers
  - ...
- sorting
  - bogosort (stupid sort)
  - bubble sort: simple, kind of slow but still usable sorting algorithm
  - heap sort
  - insertion sort
  - merge sort
  - shaker sort
  - selection sort
  - slow sort
  - quick sort: one of the fastest sorting algorithms
  - ...
- searching
  - binary search
  - linear search
  - ...
- other
  - A*: path searching algorithm, used by AI in many games
  - backpropagation: training of neural networks
  - fizzbuzz: problem/simple algorithm given in job interviews to filter out complete noobs
  - FFT: quickly converts signal (audio, image, ...) to its representation in frequencies, one of the most famous and important algorithms
  - Huffman coding: compression algorithm
  - Kalman filter
  - k-means: clustering algorithm
  - MD5: hash function
  - backtracking
  - minimax plus alpha-beta pruning: used by many AIs that play turn based games
  - proof of work algorithms: used by some cryptocurrencies
  - RSA
  - Shor's algorithm: quantum factorization algorithm
  - YouTube algorithm: secret algorithm YouTube uses to suggest videos to viewers, a lot of people hate it :)
  - ...

## See Also

- programming
- design pattern
- recursion