Difference between Divide & conquer and Dynamic programming

Posted By on October 27, 2014

Download PDF
Directed Acyclic Graph
0/1 Knapsack Problem

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.

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

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

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

5. Example: Merge Sort, Binary Search

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

Directed Acyclic Graph
0/1 Knapsack Problem

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com