What IS an algorithm?

• In my own words:
• A process for getting something done
• If the 'something' is a well specified, interesting, problem then:
• A process of converting all possible inputs to satisfactory outputs.

Some interesting problems:

• Recommend a movie
• Do Arithmetic
• Simplify an expression
• Win a game
• Encrypt/Decrypt a message

SORTING

• Problem: Sorting
• Inputs: A sequence of $$n$$ things $$a_1, \ldots, a_n$$
• Outputs: The permuation of the input things such that $$a'_1 \leq a'_2 \leq \ldots \leq a'_{n-1} \leq a'_n$$

Example input/output

('magnificent', 'andy', 'is')

becomes

('andy', 'is', 'magnificent')

An algorithm is the IDEA behind the program

• Language Independent
• Architecture Independent
• A process/procedure/recipe
• It is also a technology

So how can you communicate your algorithm?

In descending order of ease and ascending order of precision:

1. Natural Language
2. Pseudo-code
3. Real code

Insertion Sort in Natural Language

• Create a sorted set
• Examine an input thing
• Insert that thing into the sorted set, preserving order
• Repeat until done

Insertion Sort Working Code

See the code on IDEONE

void insertion_sort(int s[], int n){
int i, j, key;
for (i = 1; i < n; i++){
j = i-1;
key = s[i];
while ((j > -1) && (key < s[j])){
s[j + 1] = s[j];
j = j-1;
}
s[j+1] = key;
}
}

Counter-Examples

Finding just one proves that a method is incorrect!

"When struggling to prove something, spend half of your time trying to prove it wrong."
-Mark van Hoeij