An algorithm contains a set of tasks which solves a problem. An algorithm can be expressed within a finite amount of space and time[BigO].

Types

Algorithms can be vaguely classified in these type.

Brute force

Brute force implies using the definition to solve the problem in a straightforward manner. It uses all permutation and combination available.

Brute force algorithms are usually the easiest to implement, but the disadvantage of solving a problem by brute force is that it is usually very slow and can be applied only to problems where input size is small.

E.g.: String matching is an example of Brute force.

Divide and conquer

Divide and conquer consist of two parts, first of all, it divides the problems into smaller subproblems of the same type and solve them recursively and then combine them to form the solution of the original problem

E.g.: Binary Search is the most famous Divide and conquers algo.

Dynamic programming

It is also called as Recursion. Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial. For example, if we write a simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.

Greedy algorithm

The greedy algorithm is an algorithm that solves the problem by taking an optimal solution at the local level (without regards to any consequences) with the hope of finding an optimal solution at the global level.

The 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

Backtracking algorithm

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree).

For example, consider the SudoKo solving Problem, we try filling digits one by one. Whenever we find that current digit cannot lead to a solution, we remove it (backtrack) and try the next digit.

Branch and Bound Algorithm

Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems are typically exponential in terms of time complexity and may require exploring all possible permutations in the worst case. The Branch and Bound Algorithm technique solve these problems relatively quickly.

For E.g.,

Traveling Salesman Problem

Each node of the state space tree is a list of the cities visited currently. The root can be any single city. Traveling along an edge in the graph adds the destination city to the list at the next level node.

We need a lower bound for the tour distance. First, consider a lower bound function for the root of the state tree.

One lower bound could be multiplying the smallest intercity distance by the number of cities. This lower bound is clearly too low.

A better algorithm would be to use the sum of the average distance between the city and the two nearest adjacent cities for each city.

Show example

This is a lower bound because any tour must approach and leave the city by paths at least this long. It also clear that this bounding function is larger than the previous.

As cities are added to the tour, the bounding function uses the average of the used edge with the remaining nearest city.

Show example

We can use an additional trick. Because the graph is undirected we can eliminate half of the paths by considering a path that travels only one direction between two cities. To implement the algorithm picks two cities, for example, band c, and considers the only path with b proceeding c.