What are the fundamental techniques used to design an algorithm efficiently. Also write two problems for each that follows these techniques.

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

               (i) Divide and Conquer

               (ii) Greedy method

              (iii) Dynamic Programming

              (iv) Backtracking

              (v) Branch and Bound

(i) Divide and Conquer: Divide and conquer technique is a top-down approach to solve a problem. It requires 3 steps.

·                      Divide, the original problem into a set of sub problems.

·                      Conquer every sub-problem individually, recursive.

·                      Combine, the solutions of these sub problems to get the solution of original problem.

(ii) Greedy method: Greedy method 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 w. r. t. some constraints or conditions. The greedy algorithm does not always guaranteed the optimal solution.

(iii) Dynamic Programming: Dynamic programming technique is similar to divide and conquer approach. Dynamic programming is a Bottom-up approach that begins by solving the smaller sub-problem, saving these partial result and then reusing them to solve larger sub-problems until the solution to the original problem is obtained. The dynamic programming approach always gives a guarantee to get an optimal solution.

(iv) Backtracking: 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.

(v) Branch and Bound: Branch and Bound (B&B): B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail. Branch and bound is a systematic method for solving optimization problems.

Two problems for each that follows those techniques are given below:-

Design strategy	Problems that follows
Divide & Conquer	(i) Binary search (ii) Merge sort
Greedy method	(i) Knapsack problem (ii) Minimum cost spanning tree  *                     Kruskal’s algorithm   *                     Prim’s algorithm
Dynamic programming	(i) 0/1 Knapsack problem (ii) Chain matrix multiplication
Backtracking	(i) N-queen’s problem (ii) Sum of subset
Branch & Bound	(i) Assignment problem (ii) Traveling Salesmen Problem (TSP)