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 [1]programming is all
about: we tell [2]computers, in very exact ways (with [3]programming
languages), how to solve problems -- we write algorithms. But algorithms
don't have to be just computer programs, they are simply exact instruction
for solving problems. Although maybe not as obvious, [4]mathematics is
also a lot about creating algorithms because it strives to give us exact
instructions for solving problems -- a mathematical formula usually tells
us what we have to do to compute something, so in a way it is an algorithm
too.
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 [5]maze which doesn't have any disconnected walls: you just pick
either a left-hand or right-hand wall and then keep following it. 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 [6]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 [7]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
[8]undecidability, but for most practically encountered problems we can
write an algorithm (though for some problems even our best algorithms can
be unusably [9]slow).
Algorithms are mostly (possibly [10]not always, depending on exact
definition of the term) written 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
([11]machine code, [12]assembly) computers cannot do anything more complex
than that: execute simple instructions (expressed as [13]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 [14]branches (in programming
known as if-then-else) and [15]loops. Branches and loops are together
known as [16]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.").
Note: in a wider sense algorithms may be expressed in other
(mathematically equivalent) ways than sequences of steps
(non-[17]imperative ways, see [18]declarative languages), even
mathematical equations are often called algorithms because they imply the
steps towards solving a problem. But we'll stick to the common narrow
meaning of algorithm given above.
Additional constructs can be introduced to make programming more
comfortable, e.g. [19]subroutines/functions (kind of small subprograms
that the main program uses for solving the problem), [20]macros (shorthand
commands that represent multiple commands) or [21]switch statements
(selection but 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 [22]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 [23]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 [24]text, but
visual programming is also possible: [25]flowcharts are a way of visually
expressing algorithms, you have probably seen some. [26]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 [27]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
[28]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 [29]prime along the way. (Note that
we'll do it in a [30]naive, educational way -- it can be done better).
Let's start by writing the steps in plain [31]English (sometimes called
[32]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
[33]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 [34]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 [35]C as:
#include <stdio.h>
int main(void)
{
int x, divisors = 0;
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;
}
and in [36]comun as (for simplicity only works for numbers up to 9):
<- "0" - # read X and convert to number
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 "0" + -> 10 ->
$1 2 = ?
0 "It is a prime" --> 10 ->
.
This algorithm is however not very efficient and could be [37]optimized --
for example there is no need to check divisors higher than the square root
of the checked value (mathematically above square root the only divisor
left is the number itself) so we could lower the number of the loop
iterations and so make the algorithm finish faster.
Study of Algorithms
Algorithms are the essence of [38]computer science, there's a lot of
theory and knowledge about them.
[39]Turing machine, a kind of mathematical bare-minimum computer, created
by [40]Alan Turing, is the traditional formal tool for studying
algorithms, though many other [41]models of computation exist. From
theoretical computer science we know not all problems are [42]computable,
i.e. there are problems unsolvable by any algorithm (e.g. the [43]halting
problem). [44]Computational complexity is a theoretical study of resource
consumption by algorithms, i.e. how fast and memory efficient algorithms
are (see e.g. [45]P vs NP). [46]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 [47]dynamic programming (practical [48]optimization is a
more pragmatic approach to making algorithms more efficient). [49]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). [50]Genetic programming
and some other methods of [51]artificial intelligence try to automatically
create algorithms (algorithms that create algorithms). [52]Quantum
computing is concerned with creating new kinds of algorithms for quantum
computers (a new type of still-in-research computers). [53]Programming
language design is the art and science of creating languages that express
computer algorithms well.
Specific Algorithms
Following are some well known algorithms.
* [54]graphics
* [55]DDA: line drawing algorithm
* [56]discrete Fourier transform: extremely important algorithm
expressing signals in terms of frequencies
* [57]Bresenham's algorithm: another line drawing algorithm
* [58]Midpoint algorithm: circle drawing algorithm
* [59]flood fill: algorithm for coloring continuous areas
* [60]FXAA
* [61]Hough transform: finds shapes in pictures
* [62]painter's algorithm
* [63]path tracing
* [64]ray tracing
* ...
* [65]math
* [66]Boot'h algorithm: algorithm for multiplication
* [67]Dijkstra's algorithm
* [68]Euclidean algorithm: computes greatest common divisor
* [69]numerical algorithms: approximate mathematical functions
* [70]sieve of Eratosthenes: computes [71]prime numbers
* ...
* [72]sorting
* [73]bogosort (stupid sort)
* [74]bubble sort: simple, kind of slow but still usable sorting
algorithm
* [75]heap sort
* [76]insertion sort
* [77]merge sort
* [78]shaker sort
* [79]selection sort
* [80]slow sort
* [81]quick sort: one of the fastest sorting algorithms
* ...
* [82]searching
* [83]binary search
* [84]linear search
* ...
* [85]other
* [86]A*: path searching algorithm, used by [87]AI in many
[88]games
* [89]backpropagation: training of [90]neural networks
* [91]fizzbuzz: problem/simple algorithm given in job interviews to
filter out complete [92]noobs
* [93]FFT: quickly converts signal (audio, image, ...) to its
representation in frequencies, one of the most famous and
important algorithms
* [94]Huffman coding: [95]compression algorithm
* [96]Kalman filter
* [97]k-means: [98]clustering algorithm
* [99]MD5: [100]hash function
* [101]backtracking
* [102]minimax plus [103]alpha-beta pruning: used by many [104]AIs
that play turn based games
* [105]proof of work algorithms: used by some [106]cryptocurrencies
* [107]RSA
* [108]Shor's algorithm: [109]quantum factorization algorithm
* [110]YouTube algorithm: secret algorithm YouTube uses to suggest
videos to viewers, a lot of people hate it :)
* ...
See Also
* [111]programming
* [112]design pattern
* [113]recursion
Links:
1. programming.md
2. computer.md
3. programming_language.md
4. math.md
5. maze.md
6. woman.md
7. heuristic.md
8. undecidability.md
9. time_complexity.md
10. declarative.md
11. machine_code.md
12. assembly.md
13. binary.md
14. branch.md
15. loop.md
16. control_structure.md
17. imperative.md
18. declarative.md
19. function.md
20. macro.md
21. switch.md
22. c.md
23. variable.md
24. text.md
25. flowchart.md
26. decision_tree.md
27. snap.md
28. programming_language.md
29. prime.md
30. naive.md
31. english.md
32. pseudocode.md
33. variable.md
34. python.md
35. c.md
36. comun.md
37. optimization.md
38. compsci.md
39. turing_machine.md
40. turing.md
41. model_of_computation.md
42. computability.md
43. halting_problem.md
44. computational_complexity.md
45. p_vs_np.md
46. mathematical_programming.md
47. dynamic_programming.md
48. optimization.md
49. formal_verification.md
50. generic_programming.md
51. ai.md
52. quantum.md
53. programming_language.md
54. graphics.md
55. dda.md
56. fourier_transform.md
57. bresenham.md
58. midpoint_algorithm.md
59. flood_fille.md
60. fxaa.md
61. hough_transform.md
62. painters_algorithm.md
63. path_tracing.md
64. ray_tracing.md
65. math.md
66. booths_algorithm.md
67. dijkstras_algorithm.md
68. euclidean_algorithm.md
69. numerical.md
70. sieve_of_eratosthenes.md
71. prime.md
72. sorting.md
73. bogosort.md
74. bubble_sort.md
75. heap_sort.md
76. insertion_sort.md
77. merge_sort.md
78. shaker_sort.md
79. selection_sort.md
80. slow_sort.md
81. quick_sort.md
82. searching.md
83. binary_search.md
84. linear_search.md
85. other.md
86. a_start.md
87. ai.md
88. game.md
89. backpropagation.md
90. neural_net.md
91. fizzbuzz.md
92. noob.md
93. fft.md
94. huffman_code.md
95. compression.md
96. kalman_filter.md
97. k_means.md
98. clustering.md
99. md5.md
100. hash.md
101. backtracking.md
102. minimax.md
103. alpha_beta.md
104. ai.md
105. proof_of_work.md
106. crypto.md
107. rsa.md
108. shors_algorithm.md
109. quantum.md
110. youtube.md
111. programming.md
112. design_pattern.md
113. recursion.md