Home »
Algorithms
Algorithm and Its Types
Algorithms: In this tutorial, we will learn about the algorithms, and the various types of algorithms with the help of examples.
By Shubham Singh Rajawat Last updated : August 12, 2023
An algorithm is a set of self contained sequence of instructions or actions that contains finite space or sequence and that will give us a result to a specific problem in a finite amount of time.
It is a logical and mathematical approach to solve or crack a problem using any possible method.
Types of algorithm
Well there are many types of algorithm but the most fundamental types of algorithm are:
- Recursive algorithms
- Dynamic programming algorithm
- Backtracking algorithm
- Divide and conquer algorithm
- Greedy algorithm
- Brute Force algorithm
- Randomized algorithm
1) Simple recursive algorithm
Solves the base case directly and then recurs with a simpler or easier input every time (A base value is set at the starting for which the algorithm terminates).
It is use to solve the problems which can be broken into simpler or smaller problems of same type.
Example:
To find factorial using recursion, here is the pseudo code:
Fact(x)
If x is 0 /*0 is the base value and x is 0 is base case*/
return 1
return (x*Fact(x-1)) /* breaks the problem into small problems*/
2) Dynamic programming algorithm
A dynamic programming algorithm (also known as dynamic optimization algorithm) remembers the past result and uses them to find new result means it solve complex problems by breaking it down into a collection of simpler subproblems, then solving each of those subproblems only once ,and storing their solution for future use instead of recomputing their solutions again.
Example:
Fibonacci sequence, here is the pseudo code :
Fib(n)
if n=0
return 0
else
prev_Fib=0,curr_Fib=1
repeat n-1 times /*if n=0 it will skip*/
next_Fib=prev_Fib+curr_Fib
prev_Fib=curr_Fib
curr_Fib=new_Fib
return curr_Fib
3) Backtracking algorithm
How about we learn backtracking using an example so let’s say we have a problem “Monk” and we divide it into four smaller problems “M, R, A, A”. It may be the case that the solution of these problems did not get accepted as the solution of “Monk”.
In fact we did not know on which one it depends. So we will check each one of them one by one until we find the solution for “Monk”.
So basically we attempt solving a subproblem but if we did not reach the desired solution undo whatever you have done and start from the scratch again until you find the solution.
Example:
Queens Problem
4) Divide and conquer algorithm
Divide and conquer consist of two parts first of all it divides the problems into smaller subproblems of the same type and solve them solve them recusively and then combine them to to form the solution of the original problem.
Example:
Quick sort, Merge sort
5) Greedy algorithm
Greedy algorithm is an algorithm that solves the problem by taking optimal solution at the local level (without regards for any consequences) with the hope of finding optimal solution at the global level.
Greedy algorithm is used to find the optimal solution but it is not necessary that you will definitely find the optimal solution by following this algorithm.
Like there are some problems for which an optimal solution does not exist (currently) these are called NP complete problem.
Example:
Huffman tree, Counting money
6) Brute force algorithm
A brute force algorithm simply tries all the possibilities until a satisfactory solution is found.
Such types of algorithm are also used to find the optimal (best) solution as it checks all the possible solutions.
And also used for finding a satisfactory solution (not the best), simply stop as soon as a solution of the problem is found.
Example:
Exact string matching algorithm
7) Randomized algorithm
A randomized algorithm uses a random number at least once during the computation to make a decision.
Example:
Quick sort
As we use random number to choose the pivot point.