Best Information for Learners

DAA Complete 2 units Click Here 

CLICK HERE 

  v    Divide and Conquer: Ø   In divide and conquer approach, the problem is divided into smaller sub-problems and then each problem is solved independently. When we keep on dividing the sub-problems into even smaller sub-problems, we may eventually reach a stage where no more division is possible. Ø   Those "atomic" smallest possible sub-problems (fractions) are solved. The solution of all sub-problems is finally merged in order to obtain the solution of an original problem. Ø    Broadly, we can understand divide-and-conquer approach in a three-step process. Divide/Break Ø   This step involves breaking the problem into smaller sub-problems. Sub-problems should represent a part of the original problem. This step generally takes a recursive approach to divide the problem until no sub-problem is further divisible. At this stage, sub-problems become atomic in nature but still represent some part of the actual problem. Conquer/Solve Ø   This step

  FEASIBLE SOLUTION,OPTIMAL SOLUTION AND OBJETIVE FUNCTION:  A) Feasible Solution:  A solution (set of values for the decision variables) for which all of the constraints in the Linear Programming problem are satisfied is called a feasible solution. It is subset of a solution which satisfies restrictions applied to the problem Linear programming (LP) (also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.  B) Optimal Solution:  An optimal solution is a feasible solution where the objective function reaches its maximum (or minimum) value – for example, the most profit or the least cost. A globally optimal solution is one where there are no other feasible solutions with better objective function values. A locally optimal solution is one where there are no other feasible solutions “in the vicinity” with better objective function values A solution th

  DYNAMIC PROGRAMMING:   Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.   Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. Mostly, these algorithms are used for optimization( the   action of making the best or most effective use of a situation or resource.) . Before solving the in-hand   sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution.   So we can say that  −   The problem should be able to be divided into smaller overlapping sub-problem.   An optimum solution can be achieved by usin