Dimensions of Algorithm Design

Andy Novocin

What IS an algorithm?

Some interesting problems:

Our first sample problem:

SORTING

Example input/output

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

becomes

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

An algorithm is the IDEA behind the program

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

Our first sorting algorithm

Insertion Sort in Natural Language

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

Learning to THINK

Find the right level of Abstraction.


Find the smallest example that captures a problem.


Imagine the problem on the largest conceivable scale.


Can you transform a problem into one you know?


Ballpark the scale of your solution.


Can you spot recursive opportunities?

Read Chapter 1 (particularly the parts missing here)


Attempt the daily problem @ cs.prof.ninja/daily


Talk to your partner about cs.prof.ninja/hw/1


Talk to programming group about cs.prof.ninja/programs/1


Next class: Asymptotic Analysis!