models-of-computation.md

Models of Computation

What is an algorithm?

• Mathematical abstraction of computer program.
• Computational procedure to solve a problem.
• Sequence of instructions to solve a problem or to perform a computation.

An algorithm is an analog of a program. Algorithms are built on top of pseudocode, which is built on top of a model of computation. While programs are built on top of programming languages which are built on top of computers. The Table below clarifies this analog between an algorithm an a program:

What is a model of computation anyway?

It is a model which allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology, and it specifies:

• what operations an algorithm is allowed to do.
• what is the cost (time, space, . . .) of each operation.
• what is the cost of an algorithm (sum of operation costs).