Criteria of Desirable Algorithms

Desirable algorithms are: simple: having low complexity, easy to conceive and implement; parallel: having computational properties which can be distributed among many machines; predictable: having an average-case execution time which is not far from its worst-case execution time; and fault-tolerant: having the quality of handling errors caused by invalid inputs.

Classifications of Algorithms

Algorithms can be classified by their complexity (space complexity and time complexity). Algorithms can be classified by their parallelism (sequential or parallel). Algorithms can be classified by their exactness (exact or inexact/heuristic).

Univariate Polynomial Evaluation using Horner Scheme

A linear-space linear-time sequential recursive algorithm for evaluating a univariate polynomial (a polynomial of one variable) is the Horner scheme: Function evaluate : (A, x) : y is, where a is the top of A, If A is empty, y is zero. Otherwise if A is a singleton, y is a. Otherwise, y is a [...]

Modular Exponentiation

Function modex : (base, power, modulo) : result is If power = 0, result is 1. Otherwise if power = 1, result is base. Otherwise, result is modex(base, power div 2, modulo) squared, modulo modulo, multiplied by modex(base, power mod 2, modulo), modulo modulo.