Algorithms

What is an Algorithm?

Definition

A procedure for performing a computation broken into a well-specified steps

• Input: $X$ instance
• Output: $Y$ solution

Both $X$ and $Y$ should be finitely describable

Good Algorithm must produce correct answer in reasonable amount of time and space using least energy

Hierarchy of Obviousness

1. Obvious algorithms: Implicit in the problem statement
   • Brute force
   • Exhaustive Search
2. Methodical algorithms: Applying general principles and paradigms that improve algorithms for a wide variety of problems
3. Clever algorithms: Stretching the general paradigms in a way to best fit a particular problem

Types of Algorithms

• Graph Search