Algorithm refers to the sequential steps and process that should be followed to solve a problem. There can be various kinds of algorithms devised to solve different problems although in programming we consider the following important Algorithms to solve a problem.
Here is a list of the types of Algorithms to begin with:
- Brute Force algorithm
- Greedy algorithm
- Recursive algorithm
- Backtracking algorithm
- Divide & Conquer algorithm
- Dynamic programming algorithm
- Randomised algorithm
Brute Force Algorithm
The simplest possible algorithm that can be devised to solve a problem is called the brute force algorithm. To device an optimal solution first we need to get a solution at least and then try to optimise it. Every problem can be solved by brute force approach although generally not with appreciable space and time complexity.
Later we will see this time complexity to be reduced to O (logn).
In this algorithm, a decision is made that is good at that point without considering the future. This means that some local best is chosen and considers it as the global optimal. There are two properties in this algorithm.
- Greedily choosing the best option
- Optimal substructure property: If an optimal solution can be found by retrieving the optimal solution to its subproblems.
Greedy Algorithm does not always work but when it does, it works like a charm! This algorithm is easy to device and most of the time the simplest one. But making locally best decisions does not always work as it sounds. So, it is replaced by a reliable solution called Dynamic Programming approach.
- Sorting: Selection Sort, Topological sort
- Prim’s & Kruskal’s algorithms
- Coin Change problem
- Fractional Knapsack Problem
- Job Scheduling algorithm
For better understanding lets go through the most common problem i.e. Job scheduling problem: Let us consider a situation where we are given the starting and end times of various events in an auditorium. Now your job is to maximise the number of events that can be organised in the auditorium where no two events overlap ( starting time or ending time of one event does not fall in between the starting and endpoint of another event).
We consider six such events:
Now a brute force solution would make us think that if we sort the events by their starting times & starting with the first event while excluding all events which overlap the previous will certainly give a solution but it wont maximise the number of events. Let us see, after sorting by starting time –
So, the events that can be organised are – A, F. So, our brute force approach will have multiple such cases and fail if we don’t select the optimal initial event. Now let’s see what our greedy algorithm suggests. According to greedy algorithm we sort the events by their ending times, i.e. we select events which ends first. Our new event table will become:
So, we choose – B, E, C which is certainly a larger number of events than previous. Hence in such cases, the Greedy Algorithm gives the best solution to this type of problem.
This is one of the simplest to devise algorithm as it does not require to specifically think about every subproblem. This means we just need to think about the existing cases and the solution of the simplest subproblem, all other complexity will be handled by it automatically. Recursion is a very powerful tool although we should always take care of memory management here as recursion works using recursive stack which is called every time recursion function is invoked. Recursion simply means calling itself to solve its subproblems.
Time Complexity: O(n)
Although always remember to give the base case else the loop will continue to infinity giving memory error. This algorithm is simpler to design and implement.
It is an improvement to the brute force approach. Here we start with one possible option out of many available and try to solve the problem if we are able to solve the problem with the selected move then we will print the solution else we will backtrack and select some other and try to solve it. It is a form of recursion, it’s just that when a given option cannot give a solution, we backtrack to the previous option which can give a solution and proceed with other options.
- Generating all Binary strings
- N-Queens Problem
- Knapsack Problem
- Graph colouring Problem
Let us see the application of this algorithm in generating all strings with n bits.
Divide & Conquer Algorithm
This is one of the most used algorithms in programming. This algorithm divides the problems into subproblems and then solve each of them and then combine them to form the solution of the given problems.
Again, it is not possible to solve all problems using it. As the name suggests it has two parts: Divide the problem into subproblems and solve them.
- Combine the solution of each above problems.
- This algorithm is extensively used in various problems as it is quite stable and optimal for most of the problems asked.
The given problem is divided into two parts of n/a and n/b size and then computed separately and recursively to bring back the result and combine them to form the solution.
- Binary Search
- Merge Sort & Quick Sort
- Median Finding
- Matrix Multiplication
- Let us discuss the simplest application of Binary Search. Previously we described how searching of an element in a sorted array takes O(n) time, this time we apply divide and conquer algorithm to reduce its complexity to O(logn).
The flow of the program moves to the right subarray as five is greater than the current mid (3) and hence doesn’t iterate over half of the elements and hence reduces the time complexity. Although this is not applicable if the array is not sorted as it can be understood it will just neglect one part of the array and the algorithm will fail.
This is the most sought out algorithm as it provides the most efficient way of solving a problem. Its simply means remembering the past and apply it to future corresponding results and hence this algorithm is quite efficient in terms of time complexity.
Dynamic Programming has two properties:
- Optimal Substructure: An optimal solution to a problem contains an optimal solution to its subproblems.
- Overlapping subproblems: A recursive solution contains a small number of distinct subproblems.
This algorithm has two version:
- Bottom-Up Approach: Starts solving from the bottom of the problems i.e. solving the last possible subproblems first and using the result of those solving the above subproblems.
- Top-Down Approach: Starts solving the problems from the very beginning to arrive at the required subproblem and solve it using previously solved subproblems.
- Longest Common Subsequence, Longest Increasing Subsequence, Longest Common substring etc.
- Bellman-Ford algorithm
- Chain Matrix multiplication
- Subset Sum
- Knapsack Problem & many more.
Let us take a simple example of such algorithm. Finding the Fibonacci Sequence.
Recursive stack of the function for n = 4
Time Complexity: O(n) Space Complexity: O(n)
As we can see the dynamic programming approach gives faster result although takes up extra space. Most of the problems involving finding the nth element in a sequence can be computed faster using Dynamic programming.
This is an algorithm type which makes its decision on the basis of random numbers i.e. it uses random numbers in its logic. The best example for this is choosing the pivot element in quicksort. This randomness is to reduce time complexity or space complexity although not used regularly. Probability plays the most significant role in this algorithm.
In terms of quicksort, we fail to choose the correct element we might end up with a running time of O(n^2 ) in the worst case. Although if chosen with proper interpretation it can give the best running time of O(nlogn).
- Randomised Quick Sort
- Kager’s Algorithm etc.
To know more about the courses, click here.