Classification by Design Method

1. Greedy Method 

Greedy algorithms work in stages. In each stage, a decision is made that is good at that point, without bothering about the future consequences. Generally, this means that some local best is chosen. It assumes that the local best selection also makes for the global optimal solution.

1. Divide and Conquer 

The D & C strategy solves a problem by:

• Divide: Breaking the problem into sub problems that are themselves smaller instances of the same type of problem. 
• Recursion: Recursively solving these sub problems. 
• Conquer: Appropriately combining their answers. 

Examples: merge sort and binary search algorithms.

1. Dynamic Programming 

Dynamic programming (DP) and memoization work together. 

(Note: memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.)

The difference between DP and divide and conquer is that in the case of the latter there is no dependency among the sub problems, whereas in DP there will be an overlap of sub-problems.

By using memoization [maintaining a table for already solved sub problems], DP reduces the exponential complexity to polynomial complexity (O( n2), O( n3), etc.) for many problems.

1. Linear Programming 

In linear programming, there are inequalities in terms of inputs and maximizing (or minimizing) some linear function of the inputs. Many problems (example: maximum flow for directed graphs) can be discussed using linear programming. 

1. Reduction [Transform and Conquer] 

In this method we solve a difficult problem by transforming it into a known problem for which we have asymptotically optimal algorithms. In this method, the goal is to find a reducing algorithm whose complexity is not dominated by the resulting reduced algorithms. 

For example, the selection algorithm for finding the median in a list involves first sorting the list and then finding out the middle element in the sorted list. These techniques are also called transform and conquer.