Algorithm

A set of precise steps used to solve a problem

1. Does it do as advertised? (proving)
2. How efficient is it? (counting)

Early Algorithms

Euclid:

• Division algorithms
• Euclidean GCD algorithm

Parts of a Good Algorithm

1. Input set
2. Output set
3. "Well defined" steps (precise and clear)
4. Correctness
5. Generality (works for input values)
6. Finite-ness (eventually stops)
7. Effectiveness (each step in the algorithm works)

Classic Algorithms

Greedy Algorithms

optimize for each step

Do the best thing to get closest to goal from this current point

Halting Problem by Alan Turing

Can an algorithm determine whether an input algorithm will terminate or loop indefinitely

UNSOLVABLE!