Mumbai University > Computer Engineering > Sem 4 > Analysis of Algorithm

Marks: 10 M

Year: May 2014

Modules of computation are Dynamic Programming, Greedy method, divide & conquer, Backtracking, Branch & Bound.

I. Greedy method:

• Greedy method is straight forward method.
• A greedy method is used for obtaining optimum solution.
• In greedy method a set of feasible solutions and picks up the optimum solution.
• In greedy method the optimum selection is without revising previously generated solutions.
• In greedy method there is no as such guarantee of getting optimum solution.
• Choice of a solution made at each step of problem solving in greedy approach are:
  • Feasible: It should satisfy the problem constraint.
  • Locally optimal: Among all feasible solutions the best choice is to be made.
  • Irrevocable: Once the particular choice is made then it should not get changed on subsequent steps.

Algorithm:

Steps to solve Greedy method:

• First select some solution for input domain.
• Then check whether the solution is feasible or not.
• From the set of feasible solutions, particular solution that satisfies or nearly satisfies the objective of the function. Such a solution is called optimal solution.
• As greedy method works in stages. At each stage only one input is considered at each time. Based on this input it is decided whether particular input gives the optimal solution or not.

Applications:

• Knapsack problem.
• Prim’s & kruskal’s algorithm for minimum spanning tree.
• Job sequencing with deadlines.
• Optimal storages on tapes.

II. Dynamic Programming:

• Dynamic Programming is also used for obtaining optimum solution.
• There is no special set of feasible solutions in this method.
• Dynamic Programming considers all possible sequences in order to obtain the optimum solution.
• It is guaranteed that the dynamic programming will generate optimal solution using principle of optimality.

Principle of optimality:

• The dynamic programming method generates optimal solution using principle of optimality.
• It states that “in an optimal sequence of decisions or choices, each subsequence must also be optimal”.
• When it is not possible to apply the principle of optimality it is almost impossible to obtain the solution using dynamic programming approach.
• For example: Finding of shortest path in a given graph uses the principle of optimality.

Steps of Dynamic Programming:

• Characterize the structure of optimal solution. This means to develop a mathematical notation that can express any solution and sub solution for given problem.
• Recursively define the value of an optimal solution.
• By using bottom up technique compute the value of optimal solution.
• Compute the optimal solution form computed information.

Applications:

• Multi state graphs.
• 0/1 knapsack problem.
• All pair shortest path.
• Flow shop scheduling.
• Traveling salesman problem.