There are many types of algorithms. It means various types of process is used for solving the problems.
1.Brute force Algorithm: This is the most basic type of algorithm. It is the approach that is done without applying any logical method for shortening the algorithm. It is the first approach that comes to the mind on seeing the problem. In Brute force, we solve the problem by applying the iterative process only for solving it without any smart approach. In this, we try every possibility without using any technique to improve it.
Example. Imagine you have a box full of treasure. It will open by entering 4 digits password, each from 0-9. Since you don’t know any of the digits, you have to use a brute force method to open the box.
So, you set all the numbers back to 0 and try them one by one: 0001, 0002, 0003, and so on until it opens. In the worst-case scenario, it would take 104, or 10,000 tries to find your combination.
A classic example in computer science is the traveling salesman problem (TSP). Suppose a salesman needs to visit 10 cities across the country. How does one determine the order in which those cities should be visited such that the total distance traveled is minimized?
The brute force solution is simply to calculate the total distance for every possible route and then select the shortest one. This is not particularly efficient because it is possible to eliminate many possible routes through clever algorithms.
The time complexity of brute force is O(mn), which is also written as O(n*m) . So, if we were to search for a string of "n" characters in a string of "m" characters using brute force, it would take us n * m tries.
- Recursive Algorithm: Recursion is the process of calling itself by the function. In recursion, the problem is broke into many subproblems and then solved one by one by calling self again and again until the problem is solved with the help of the base condition. Base condition is the last condition that is used to solve all the subproblems. A recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature. The result of one recursion is the input for the next recursion. The algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values.
Example. Factorial of a number, Fibonacci Series, Tower of Hanoi, etc.
Factorial of a number:
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
Explanation: In the above example, fact() function is calling itself again and again. When the Base condition n=1 will be reached then it will be returned to the function and all subproblems will be solved.
3. Backtracking Algorithm: In backtracking, the problem is solved in such a way that for solving problems we build a solution incrementally, one piece of time, and removes the solution that fails to satisfy the conditions of the problem at any point in time.
Example: Chess problem, N queen problem, SudoKo problem
N queen problem:
The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.
Algorithm of N queen problem:
1) Start from the leftmost column
2) If all queens are placed
return true
3) Try all rows in the current column.
Do following for every tried row.
a) If the queen can be placed safely in this row
then mark this [row, column] as part of the
solution and recursively check if placing
queen here leads to a solution.
b) If placing the queen in [row, column] leads to
a solution then return true.
c) If placing queen doesn't lead to a solution then
unmark this [row, column] (Backtrack) and go to
step (a) to try other rows.
3) If all rows have been tried and nothing worked,
return false to trigger backtracking.
