Subject: Analysis Of Algorithm

Topic: Dynamic Programming

Difficulty: High

Dynamic Programming* In computer science, mathematics, management science, economics and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space.

Dynamic programming algorithms are often used for optimization. A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem. In comparison, a greedy algorithm treats the solution as some sequence of steps and picks the locally optimal choice at each step.

For example, in the coin change problem of finding the minimum number of coins of given denominations needed to make a given amount, a dynamic programming algorithm would find an optimal solution for each amount by first finding an optimal solution for each smaller amount and then using these solutions to construct an optimal solution for the larger amount.

Dynamic Programming

1. The development of a dynamic-programming algorithm can be broken into a sequence of four steps.a. Characterize the structure of an optimal solution.b. Recursively define the value of an optimal solution. c. Compute the value of an optimal solution in a bottom-up fashion.d. Construct an optimal solution from computed information

2. Dynamic Programming is not recursive.

3. DP solves the sub problems only once and then stores it in the table.

4. In DP the sub-problems are not independent.

5. Example : Matrix chain multiplication

Divide & Conquer

1. The divide-and-conquer paradigm involves three steps at each level of the recursion: • Divide the problem into a number of sub problems.

• Conquer the sub problems by solving them recursively. If the sub problem sizes are small enough, however, just solve the sub problems in a straightforward manner.

• Combine the solutions to the sub problems into the solution for the original problem.

1. They call themselves recursively one or more times to deal with closely related sub problems.

2. D&C does more work on the sub-problems and hence has more time consumption.

3. In D&C the sub problems are independent of each other.

4. Example: Merge Sort, Binary Search