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 Algorithm 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.

Example:

Exact string matching algorithm

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

Applications

• Sorting: Selection Sort, Topological sort
• Prim’s & Kruskal's algorithm
• 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).

Recursive Algorithm

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.

For Example:

• 

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.

Backtracking Algorithm

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.

Applications

• 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.

Applications:

• 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).

Example:

 Quick sort , Merge sort.

Dynamic Algorithm

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.

Applications

• 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.

 Randomized algorithm

A randomized algorithm uses a random number at least once during the computation to make a decision.

Applications

• Randomised Quick Sort
• Kager’s Algorithm etc.

Example:

Quick sort