# Algorithms

## Definition

An algorithm is ...

• a well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.
• a sequence of computational steps that transforms the input into the output.
• a tool for solving a well-specified computational problem

## The sorting problem

Input: A sequence of $$n$$ numbers $$\langle a_1, a_2,\ldots, a_n \rangle$$.

Output: A permutation (reordering) $$\langle a'_1, a'_2,\ldots,a'_n \rangle$$ of the input sequence such that $$a'_1 \leq a'_2 \leq \cdots \leq a'_n$$.

• sorting is often used as an intermedeate step and thus a fundamental operation in computer science.
• there are a large number of available sorting algorithms

## Factors for choosing the right algorithm

• number of items to be sorted
• to which extend the items are already sorted
• possible restrictions on the item values
• computer itself

An algorithm is correct if, for every input instance, it halts with the correct output. A correct algorithms solves the given problem. An incorrect algorithm might not halt on some input instances, or it might halt with an incorrect answer.

You can specify an algorithm in different ways (English, as a computer programm, ..) as long as it meets the only requirement, that the specification provides a precise description of the computational procdure.

## Data structures

• way to store and organize data in order to access or modify it
• every data structure has its own strengths and limitations

## Hard problems

• for some problems no efficient solution exists
• problems that fall into this category are called NP-complete
• no one knows whether or not efficient algorithms exist for NP-complete problems
• if there is an efficient algorithm for one, then there is one for all

## Insertion sort

• efficient algorithm to sort a small amount of elements
• similar to sorting a hand of playing cards
• simple implementation
• most efficient in practice than other simple sorting algorithms