Classification of algorithms
Algorithms can be classified by purpose but there are some other ways to classify them like
- By implementation
- By purpose
- By complexity
- By design paradigm
Classification by Implementation
As the name suggests implementation can classify an algorithm by implementation. like we can classify the algorithm on the basis of input sets, output sets, operating systems etc. so in terms of implementation, we can classify the algorithms in 4 terms.
- Serial or Parallel
- Recursive or Iterative
- Deterministic or non-deterministic
- Logic or Procedural algorithms
Serial or Parallel
Algorithms are usually described as how a computer executes one instruction of an algorithm at a time. these types of serial algorithms use computer architectures and process several instructions at once as just opposed to parallel algorithms. in these types of algorithms, the problems are divided into sub-problems and pass through several processors to reach the result. iterative algorithms are generally parallelizable. sorting algorithms can be parallelized efficiently.
Recursive or Iterative
A recursive or iterative type of algorithm is one that runs repeatedly over and over again. and we need to set conditions to stop these types of algorithms. this method is also similar to functional programming. iterative algorithms use repetitive constructs like loops. for example, the tower of the Hanoi problem is a good example of a recursive algorithm. every iterative version has a recursive equivalent recursive, and also vice versa is true.
Deterministic or non-deterministic
Deterministic algorithms solve the problem with a predefined process whereas non-deterministic algorithms must perform guesses of the best solution at each step through the use of heuristics.
Logic or Procedural
An algorithm may be viewed as a controlled logical deduction. in these types of algorithms, a logic component is viewed as the axioms and can be used in a control component and in the computation in the way in which deduction is applied to the axioms. In logical programming languages, algorithms are specified by supplying the logic component and the control component is always fixed. and this is one of the basic features of a logic programming language.
Classification by purpose
Each algorithm has a purpose to do, for example, the purpose of the heap sort algorithm is to sort data using the Heap in ascending and descending order. but the number of goals is infinite and we have to group them by kind of purposes like algorithms and source code.
Classification by complexity
Every algorithm has some certain complexity. some algorithm may take the linear time or some take the exponential time or some algorithms never ends. also, an algorithm may take less space in comparison to another algorithm. so to select an algorithm we always need to consider the complexity of an algorithm. an algorithm always performs great if it has low space complexity and time complexity.
Classification by design
The word design paradigm means a set of problems that requires a dedicated algorithm to solve that problem. in terms of design paradigm the algorithms are divided into 7 terms.
- Divide and conquer
- Dynamic programming
- The greedy method
- Linear programming
- Reduction/transform and conquer techniques
- Probabilistic/Heuristic paradigm
Divide and conquer
The divide and conquer algorithm works on a multi-branched recursion paradigm. these types of algorithms repeatedly reduce instances of a problem to smaller problems or branches of the same problem and this process is continue till each sub-problem is not small enough to solve easily. The binary search algorithm is a suitable example to understand the divide and conquer technique. but before sorting, there are some cases to consider using the divide and conquer technique in binary search. The merge sorting algorithm is also one of the best examples of the divide and conquers technique. In the merge, the sorting problem is divided into the sub-problems. after dividing the data into segments the sorting is applied to each subproblem, and then obtained the solution by merging all of them.
Using the dynamic programming w can avoid the recomputing if a way of solving a problem is already computed then we can skip that way using the dynamic programming. for example in the weighted graph to find the shortest path we need to traverse from all adjacent vertices. so for every path, we need to find the distance of the path and then we need to select the shortest path from all the distances of paths. like the divide and conquer technique dynamic programming has also divided the problem into subproblems. but the difference is that in the divide and conquer technique all the subproblems are not overlapped each other but in the dynamic programming, it is not.
Greedy Methods also use the problem dividing technique. but like the dynamic programming in the greedy method solution to each subproblem does not know at each stage. so we can say that the greedy method and dynamic programming algorithms are almost the same. The minimum spanning tree is a good example of the greedy method.
The linear programming approach tries to maximize and minimize the inputs after the problem is expressed as a set of linear inequalities. Integer programming is also a part of linear programming where all the integers restricted the solution spaces. linear programming is one of the solutions for finding the maximum flow for directed graphs.
Reduction/Transform and Conquer techniques
As the name suggests reduction/transform techniques transform a set of problems into another problem. for example if we want to find the median of an unsorted list we need to first transform this unsorted list into a sorted list and then we can find the middle element of the list. the transform/reduction technique always aims to find the simplest and possible transformation.
Graphs are always used to solve complex problems like chess problems or backtracking problems. graphs are also used in the searching techniques that can be modelled as problems on graphs.
Probabilistic and Heuristic paradigm
As the name suggests probabilistically means picking some random group of solutions by choice and then attempting to find the solutions to problems by using the biological processes and with the generations of solutions by random mutations. these types of algorithms are used where we not to find an optimal solution but need to find the approximate solutions where we don't have time or resources to find the perfect solution in a practical way.