Algorithm Design Techniques

The main algorithm design techniques are:

Divide and Conquer

It is a top-down approach of solving problems. Algorithms designed using this approach involve three key steps:

• Divide a large problem into a set of sub-problems.
• Solve every sub-problem individually, recursively.
• Combine the solutions of the sub-problems to get the solution of original problem.

For example, Quick Sort, Merge Sort, etc.

Greedy

Greedy method is used to solve the optimization problem. An optimization problem is one in which given a set of input values, which are required either to be maximized or minimized.

As the name suggests, Greedy Algorithm always makes the choice that looks best at the moment, to optimize a given objective. The greedy algorithm doesn't always guarantee the optimal solution however it generally produces a solution that is very close to the optimal.

For example, 0/1 knapsack problem, Huffman Compression, Job Scheduling, etc.

Dynamic Programming

Dynamic Programming is a method of solving complex problems by reusing the solutions. The results obtained by solving small sub-problems is stored in memory and the complex problem is solved using those solutions.
For example: Solving Fibonacci Series by pre-computing fibonacci number for each position and storing them in an array.

Back Tracking

Backtracking Algorithm tries each possibility until they find the right solution. It is a depth-first search in the set of possible solutions. During the search, if an alternative doesn't work, then backtrack to the choice point and tries the next alternative.

For example: Path finder, 8-Queen, etc.