- 21 Eki 2015
- 477
- 1
Algorithm Types
1) 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.
Fact
If y is 0
return 1
return (y*Fact(y-1)) /* this is where the recursion happens*/
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.
Fibonacci(N) = 0 (for n=0)
= 0 (for n=1)
= Fibonacci(N-1)+Finacchi(N-2) (for n>1)
3) Backtracking Algorithm
How about we learn backtracking using an example so lets 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.
4) 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.
The algorithm has 5 components:
- The first one is a candidate set from which we try to find a solution.
- A selection function which helps choose the best possible candidate.
- A feasibility function which helps in deciding if the candidate can be used to find a solution.
- An objective function which assigns value to a possible solution or to a partial solution
- Solution function that tells when we have found a solution to the problem.
5) 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.
Algorithm S_Search (A[0..n], X)
A[n] ← X
i ← 0
While A ≠ X do
i ← i + 1
if i < n return i
else return -1
6) Randomized Algorithm
A randomized algorithm uses a random number at least once during the computation to make a decision.