Dimensions of Algorithm Design
Andy Novocin
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
Our first sample problem:
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:
- Natural Language
- Pseudo-code
- Real code
Our first sorting algorithm
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 Example
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;
}
}
Insertion Sort as a Romanian Folk Dance
Desirable Properties
Correct
Efficient (More Soon)
Simple
Correctness
This requires proving the validity of your method.
Proofs are elegant and tricky things.
You can spend a career learning proofs.
This course only has a few proof techniques.
For now we must settle with
Induction
Counter-Examples
Invariant Properties (Not in the book)
Proof by Induction
(Normally paired with recursion)
Guess a formula: \(f(n)\)
Demonstrate it on a small value: e.g. \( f(1) \)
Assume it is true up to a point: \( \forall k \leq n\)
Prove the formula past that point: e.g. \(k = n+1\)
I will work out 1-15 on Board
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