Ques : Describe Basic Techniques for Design of Efficient Algorithm ?

 There are basically 5 fundamental techniques which are used to design an algorithm efficiently:

1. Divide-and-Conquer
2. Greedy method
3. Dynamic Programming
4. Backtracking
5. Branch-and-Bound

In this section we will briefly describe these techniques with appropriate examples.

1. Divide & conquer technique is a top-down approach to solve a problem. The algorithm which follows divide and conquer technique involves 3

• steps:
  Divide the original problem into a set of sub problems.
  Conquer (or Solve) every sub-problem individually, recursive.
  Combine the solutions of these sub problems to get the solution of
  original problem.

Greedy technique is used to solve an optimization problem. An Optimization problem is one in which, we are given a set of input values, which are required to be either maximized or minimized (known as objective function) w. r. t. some constraints or conditions. Greedy algorithm always makes the choice (greedy criteria) that looks best at the moment, to optimize a given objective function. That is, it makes a locally optimal choice in the hope that this choice will lead to a overall globally optimal solution. The greedy algorithm does not always guaranteed the optimal solution but it generally produces solutions that are very close in value to the optimal.

Dynamic programming technique is similar to divide and conquer approach. Both solve a problem by breaking it down into a several sub problems that can be solved recursively. The difference between the two is that in dynamic programming approach, the results obtained from solving smaller sub problems are reused (by maintaining a table of
results) in the calculation of larger sub problems. Thus dynamic programming is a Bottom-up approach that begins by solving the smaller sub-problems, saving these partial results, and then reusing them to solve larger sub-problems until the solution to the original problem is obtained. Reusing the results of sub-problems (by maintaining a table of results) is the major advantage of dynamic programming because it avoids the recomputations (computing results twice or more) of the same problem .Thus Dynamic programming approach takes much less time than naïve or
straightforward methods, such as divide-and-conquer approach which solves problems in top-down method and having lots of re-computations. The dynamic programming approach always gives a guarantee to get a optimal solution

The term “backtrack” was coined by American mathematician D.H. Lehmer in the 1950s. Backtracking can be applied only for problems which admit the concept of a “partial candidate solution” and relatively quick test of whether it can possibly be completed to a valid solution. Backtrack algorithms try each possibility until they find the right one. It is
a depth-first-search of the set of possible solutions. During the search, if an alternative doesn‟t work, the search backtracks to the choice point, the place which presented different alternatives, and tries the next alternative.
When the alternatives are exhausted, the search returns to the previous choice point and try the next alternative there. If there are no more choice points, the search fails.

Branch-and-Bound (B&B) is a rather general optimization technique that applies where the greedy method and dynamic programming fail B&B design strategy is very similar to backtracking in that a state-spacetree is used to solve a problem. Branch and bound is a systematic method for solving optimization problems. However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case. On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average. The general idea of B&B is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines
which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found. Branch and Bound (B&B) is the most widely used tool for solving large scale NP-hard combinatorial optimization problems.