Programs take up resources (time, space, processors).  How are these
analyzed?


Algorithm - tool for solving well-specified computational problem
            (different than program)


Criteria for analysis of a program
----------------------------------
* correctness
* amount of work done (time complexity, complexity)
* amount of space needed
* simplicity
* optimality


1. correctness - halts with correct output

2. amount of work done
     Basic operations: comparisons, multiplications, etc, as opposed
     to machine specific things (mips, flops, disk accesses)
     - related to input size
     - worst case, best case, average case

3. space - extra space beyond program and input, e.g., sort that uses
    temporary space

4. simplicity - very subjective

5. optimality - no other algorithm could do better
      How show it?
      * show worst case = f(n) steps
      * show f(n) basic steps are necessary


------------------------------------------------------------

Towers of Hanoi

Problem: Varying size disks on one of three pegs.  Move all disks to
another peg given constraint of one move at a time, and can only move
smaller on top of bigger.

Look at small cases

H_1 = 1    H_2 = 3      H_3 = 7

To move 3 disks, we solve the 2 disk problem twice

To move the largest disk, we move n-1 off, move largest, then move n-1
on.

If we use optimal for n-1, then n is optimal.

H_n = 2 H_(n-1) + 1  for n>1 with H_1 = 1
(This is called a recurrence relation, later case written in terms of
 previous case(s)).

Check H_2, H_3

Write out a few
H_1=1  H_2=3  H_3=7  H_4=15  H_5=31

Guess  H_n = 2^n - 1

Prove by mathematical induction

Basis:  H_1 = 2^1 - 1 = 1

Assume true for n-1, that is, H_(n-1) = 2^(n-1) - 1

Prove for H_n:
   H_n = 2 H_(n-1) + 1 = 2 * (2^(n-1) - 1) + 1 = 2^n - 2 + 1 = 2^n -1
   qed


What have we learned?
----------------------
1. Look at small cases
2. Find recurrence relation by associating nth case with smaller cases
3. Derive or guess a solution
4. Prove the general case is correct