# Algorithm

An Algorithm is a (procedure|method) for solving a problem.

If there exists an algorithm, the function that performs it is called computable.

Study of algorithms dates at least to Euclid and were formalized by Church and Turing in 1930s.

Algorithm are procedural in nature.

To be interesting, an algorithm has to solve a general, well-specified problem by describing a method expressed as a finite sequence of instructions.

Algorithms are used for calculation, data processing, and many other fields.

(In more advanced or abstract settings, the instructions do not necessarily constitute a finite sequence, and even not necessarily a sequence; see, e.g., nondeterministic algorithm)

The relationship between a function and a algorithm is that a function has one or many algorithm to return a result.

Algorithms are instructions for single agents. Protocols are instructions for multiple agents.

Manuel Blum #hlf14

An algorithm must be seen to be believed

Donald Knuth

Algorithms + Data Structures = Programs.

Niklaus Wirth

The difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

Linus Torvalds

Perhaps the most important principle for the good algorithm designer is to refuse to be content.

Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms, 1974

Can we do better than the obvious solution ?

Tim Roughgarden

## Example

An animation of the quicksort algorithm sorting an array of randomized values. The red bars mark the pivot element; at the start of the animation, the element farthest to the right hand side is chosen as the pivot.

## List

Data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes.

A function for summarizing or probabilistically identifying data. Typically this means one applies a mathematical formula to the data, producing a string which is probably more or less unique to that data. The string is much shorter than the original data, but can be used to uniquely identify it.

A sorting algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e.g. file streams) into a specified order.

• Algorithmic Skeletons are a high-level parallel programming model for parallel and distributed computing which take advantage of common programming patterns to hide the complexity of parallel and distributed applications. Starting from a basic set of patterns (skeletons), more complex patterns can be built by combining the basic ones.
• k-modes: Bell Labs algorithm, first used in 1998 to analyze diseased soybean crops