An algorithmic paradigm is a generic method or approach which underlies the design of a class of algorithms.
It is an abstraction higher than the notion of an algorithm.
This is like an algorithm is an abstraction higher than a computer program.
Examples of algorithmic paradigms
greedy algorithms : greedy approach
dynamic programming
divide and conquer algorithms
prune and search
...
Greedy algorithms
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
Fortunately, some greedy algorithms (such as Kruskal's or Prim's for minimum spanning trees) are proven to lead to the optimal solution.
The greedy algorithm of coin change problem gives a non-optimal solution.Â
Dynamic programming
Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. The technique of storing solutions to subproblems instead of recomputing them is called "memoization".
A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem.
Divide and conquer algorithm
In computer science, divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
Prune and search
The basic idea of the method, prune and search, is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor 0 < p < 1.
Let n be the input size, T(n) be the time complexity of the whole prune-and-search algorithm, and S(n) be the time complexity of the pruning step. Then T(n) obeys the following recurrence relation:
T(n)=S(n)+T(n(1-p)).
This resembles the recurrence for binary search but has a larger S(n) term than the constant term of binary search. In prune and search algorithms S(n) is typically at least linear.
