Introduction to Dynamic Programming, Principle of Optimality

Introduction
Dynamic Programming
How Dynamic Programming reduces computation
Steps in Dynamic Programming
Dynamic Programming Properties
Principle of Optimality
Problem solving using Dynamic Programming

1. Prepared by- Bhavin Darji Guided by – SUBJECT-ADA (2150703) Introduction to Dynamic Programming, Principle of Optimality

2. Introduction Typically applied to optimization problem. Invented by a U.S. Mathematician Richard Bellman in 1950. In the word Dynamic Programming the word programming stands for planning.

3. Dynamic Programming is technique for solving problems with overlapping subproblems. In this method each subproblem is solved only once. The result of each subproblem is recorded in a table from which we can obtain a solution to the original problem. In Dynamic computing duplications in solution is avoided totally. Efficient then Divide and conquer strategy. Uses bottom up approach of problem solving.

4. Dynamic Programming Dynamic Programming is an algorithm design technique for optimization problems: often minimizing or maximizing. Like divide and conquer, DP solves problems by combining solutions to subproblems. Unlike divide and conquer, subproblems are not independent. Subproblems may share subproblems However, solution to one subproblem may not affect the solutions to other subproblems of the same problem.

5. DP reduces computation by Solving subproblems in a bottom-up fashion . Storing solution to a subproblem the first time it is solved . Looking up the solution when subproblem is encountered again.

6. Key Idea The key idea is to save answers of overlapping smaller sub-problems to avoid recomputation. determine structure of optimal solutions.

7. Steps in Dynamic Programming Characterize structure of an optimal solution. Define value of optimal solution recursively. Compute optimal solution values either top-down with caching or bottom-up in a table. Construct an optimal solution from computed values.

8. Dynamic Programming Properties An instance is solved using the solutions for smaller instances. The solutions for a smaller instance might be needed multiple times, so store their results in a table. Thus each smaller instance is solved only once. Additional space is used to save time.

9. Principle of Optimality Obtains the solution using principle of optimality. 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 the dynamic programming approach. Example: Finding of shortest path in a given graph uses the principle of optimality.

10. Problem solving using Dynamic Programming Various problem that can be solved using dynamic programming are- Calculating the Binomial coefficient Making change problem Assembly line scheduling Knapsack problem Shortest path Matrix chain Multiplication

11. Thank You 