Introduction to Algorithms
An Algorithm is a sequence of steps that describe how a problem can be solved. Every computer program that ends with a result is basically based on an Algorithm. Algorithms, however, are not just confined for use in computer programs, these can also be used to solve mathematical problems and on many matters of day-to-day life. Based on how they function, we can divide Algorithms into multiple types. Let’s take a look at some of the important ones.
Types of Algorithm
There are many types of Algorithms but the fundamental types of Algorithms are:
1. Recursive Algorithm
This is one of the most interesting Algorithms as it calls itself with a smaller value as inputs which it gets after solving for the current inputs. In more simpler words, It’s an Algorithm that calls itself repeatedly until the problem is solved.
Problems such as the Tower of Hanoi or DFS of a Graph can be easily solved by using these Algorithms.
For example, here is a code that finds a factorial using a recursion Algorithm:
Fact(y)
If y is 0
return 1
return (y*Fact(y-1)) /* this is where the recursion happens*/
2. Divide and Conquer Algorithm
This is another effective way of solving many problems. In Divide and Conquer algorithms, divide the algorithm into two parts, the first parts divides the problem on hand into smaller subproblems of the same type. Then on the second part, these smaller problems are solved and then added together (combined) to produce the final solution of the problem.
4.6 (3,144 ratings)
View Course
Merge sorting and quick sorting can be done with divide and conquer algorithms. Here is the pseudocode of the merge sort algorithm to give you an example:
MergeSorting(ar[], l, r)
If r > l
- Find the mid-point to divide the given array into two halves:
middle m = (l+r)/2
- Call mergeSorting for the first half:
Call mergeSorting(ar, l, m)
- Call mergeSorting for the second half:
Call mergeSorting(ar, m+1, r)
- Merge the halves sorted in step 2 and 3:
Call merge(ar, l, m, r)
3. Dynamic Programming Algorithm
These algorithms work by remembering the results of the past run and using them to find new results. In other words, dynamic programming algorithm solves complex problems by breaking it into multiple simple subproblems and then it solves each of them once and then stores them for future use.
Fibonacci sequence is a good example for Dynamic Programming algorithms, you can see it working in the pseudo code:
Fibonacci(N) = 0 (for n=0)
= 0 (for n=1)
= Fibonacci(N-1)+Finacchi(N-2) (for n>1)
4. Greedy Algorithm
These algorithms are used for solving optimization problems. In this algorithm, we find a locally optimum solution (without any regard for any consequence in future) and hope to find the optimal solution at the global level.
The method does not guarantee that we will be able to find an optimal solution.
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.
Huffman Coding and Dijkstra’s algorithm are two prime examples where Greedy algorithm is used.
In Huffman coding, The algorithm goes through a message and depending on the frequency of the characters in that message, for each character, it assigns a variable length encoding. To do Huffman coding, we first need to build a Huffman tree from the input characters and then traverse through the tree to assign codes to the characters.
5. Brute Force Algorithm
This is one of the simplest algorithms in the concept. A brute force algorithm blindly iterates all possible solutions to search one or more than one solution that may solve a function. Think of brute force as using all possible combinations of numbers to open a safe.
Here is an example of Sequential Search done by using brute force:
Algorithm S_Search (A[0..n], X)
A[n] ← X
i ← 0
While A [i] ≠ X do
i ← i + 1
if i < n return i
else return -1
6. Backtracking Algorithm
Backtracking is a technique to find a solution to a problem in an incremental approach. It solves problems recursively and tries to get to a solution to a problem by solving one piece of the problem at a time. If one of the solutions fail, we remove it and backtrack to find another solution.
In other words, a backtracking algorithm solves a subproblem and if it fails to solve the problem, it undoes the last step and starts again to find the solution to the problem.
N Queens problem is one good example to see Backtracking algorithm in action. The N Queen Problem states that there are N pieces of Queens in a chess board and we have to arrange them so that no queen can attack any other queen in the board once organized.
Now let’s take a look at SolveNQ algorithm and Check Valid functions to solve the problem:
CheckValid(Chessboard, row, column)
Start
If there is a Queen at on the left of the current column then return false
If the queen is at upper-left diagonal, then return false
If the queen is at lower-left diagonal, then return false
Return true
End
SolveNQ(Board, Column)
Start
If all columns are full then return true
For each row present in the chess board
Do
If, CheckValid( board, x, column), then
Set the queen at cell (x, column) on the board
If SolveNQ(board, column+1) = True, then return true.
Else, remove the queen from the cell ( x, column) from board
Done
Return false
End
Conclusion
Algorithms are behind most of the impressive things computers can do and these are at the core of most computing tasks. Being better with algorithms will not only help you in being a successful programmer, but you will become more efficient as well.
Recommended Articles
This has been a guide to Types of Algorithms. Here we discuss the Top 6 important types of Algorithms with their functions in detail. You can also go through our other suggested articles to learn more –
