Algorithms
Gerald Farin & Dianne Hansford


Algorithm: step-by-step procedure for solving a problem.

Properties:
- unambiguous
- terminaring
- complete

- Will a given algorithm encounter an infinite loop? Unsolvable.
- “Hard” problem: triangulating a set of points.
- Unknown (but hard) complexity: traveling salesman problem.

Recursion: Ackermann’s function (used in Computer Graphics)
- grows extremely fast
- extends addition, multiplication, exponentiation, ...

A[0, 1, x_] := x + 1;
 A[k_, 1, x_] := A[k - 1, x, x]; 
A[k_, i_, x_] := Nest[Function[y, A[k, 1, y]], x, i];

Function Growth

This notebook demonstrates the growth of the polynomials, logarithmic, and exponential functions that are typical big-O categories of computing time.

Manipulate[
Plot[{Log[n],n, n*Log[n], n*n, n^3, 2^n}, {n,1,range},  ImageSize->800,
AxesStyle->Directive[FontFamily->"Helvetica", 20], PlotRange->All, PlotStyle->{Directive[Red,Thick], Directive[Green,Thick], Directive[Blue,Thick], Directive[Yellow,Thick], Directive[Cyan,Thick], Directive[Magenta,Thick]},PlotLegends->Placed[{Style["logn", 20,  FontFamily->"Helvetica"], Style["n", 20,  FontFamily->"Helvetica"], Style["nlogn", 20,  FontFamily->"Helvetica"], Style["n^2", 20,  FontFamily->"Helvetica"], Style["n^3", 20,  FontFamily->"Helvetica"], Style["2^n", 20,  FontFamily->"Helvetica"]},Bottom]],
{range,2,20}]