## 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**