Describe divided and that dynamics respectively (b) What does a dynamic programm

Question

Describe divided and that dynamics respectively (b) What does a dynamic programming technique is conquer technique and dynamic programming ? What is a difference between the two technique ? (c) When do you use divided - and - conquered and when do you use dynamic programming when you solve a programming? Function C (x, y) is defined as follows: C (i, 0) - C (0, j) - 2 for n greaterthanorequalto i greaterthanorequalto 0 & & n greaterthanorequalto j greaterthanorequalto 0 C (i, j) - max {C (i - i - j +1) +, C (i - l - j), C (i, j - 1) for n greaterthanorequalto 0 & & n greaterthanorequalto 0 (a) Finish the following table: (b) Write the algorithm to calculate C (i, j) for n greaterthanorequalto i greaterthanorequalto 0 & & n greaterthanorequalto j greaterthanorequalto 0 using Dynamic Programming technique. Analyze the time complexity of your algorithm.

Explanation / Answer

Describe divide and conquer technique and the dynamic programming technique respectively.
The divide and conquer problem divides the original problem into smaller subproblems, usually
equal sizes (if possible), and the subproblems are solved. Finally, the subproblem solutions
are combined together to form the solution to the original problem.

Coming to dynamic problem, here again the problem is divided into smaller parts. But here
it will not employ recursion to solve the same problem again and again. Instead the sub-problem
results are saved to a table (memory), so that the previous subproblem solutions are used
to solve the current problem, and thereby saving the time.

What does a dynamic programming technique have in common with divide and conquer technique?
What is a principal difference between the two techniques.
Both in dynamic programming technique and Divide and conquer technique, the problem is
divided into subparts, and the subproblems are solved first to achieve the solution to the
original problem.
The principal difference between dynamic programming and divide and conquer is that, D & Q
uses recursion (most of the times) technique to solve the subproblems, and thereby uses
stack to solve the problem, where as in dynamic programming, it saves the previously
solved subproblems solutions, so that the values can be re-used instead of calculating
the values everytime required.

When do you use divide and conquer and when do you use dynamic programming when you
solve a problem.
Usually when the subproblems are independent on one another the divide and conquer technique
is used, where as when the subproblems are dependent, the dynamic programming technique
is preferred.
D&Q is best when there is no overlapping subproblems, and when stack is not a constraint.
Where as Dynamic programming is used when processing power is a constraint, but at the cost
of some extra space to store the previous results.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.