Dynamic Programming vs. Divide and Conquer

Page 1 of 1

6 Replies - 20439 Views - Last Post: 23 March 2009 - 06:57 AM

#1 stratack

Reputation: 0
• Posts: 24
• Joined: 16-December 08

Dynamic Programming vs. Divide and Conquer

Posted 27 February 2009 - 08:34 AM

Hi,

I really need some compare with two algorithms Dynamic programming and Divide and conquer.
Some simple example that will explain me difference between this two algorithm.
Is This A Good Question/Topic? 0

Replies To: Dynamic Programming vs. Divide and Conquer

#2 Hyper

• Banned

Reputation: 108
• Posts: 2,129
• Joined: 15-October 08

Re: Dynamic Programming vs. Divide and Conquer

Posted 27 February 2009 - 08:37 AM

[rules]Care to be more descriptive with some form of example or work you have already...?[/rules]

• Saucy!

Reputation: 6187
• Posts: 23,912
• Joined: 23-August 08

Re: Dynamic Programming vs. Divide and Conquer

Posted 27 February 2009 - 08:45 AM

Modified title to be more descriptive and moved to Software Development.

#4 stratack

Reputation: 0
• Posts: 24
• Joined: 16-December 08

Re: Dynamic Programming vs. Divide and Conquer

Posted 28 February 2009 - 06:16 AM

Ok, thnx at all, so anybody of you will help me ?
Where is difference between dynamic programming and divide and conquer
which one is the best? I will appreciate your opinion ?

#5 shangyi

Reputation: 5
• Posts: 28
• Joined: 15-June 08

Re: Dynamic Programming vs. Divide and Conquer

Posted 28 February 2009 - 09:11 AM

stratack, on 28 Feb, 2009 - 05:16 AM, said:

Ok, thnx at all, so anybody of you will help me ?
Where is difference between dynamic programming and divide and conquer
which one is the best? I will appreciate your opinion ?

In my opinion divide and conquer approach (structure charts) is the best method.

Why? the structure chart shows how we are going to break our program into logical steps; each step will be a separate module. The structure chart shows the interaction between all the parts (modules of our program). It is important to realize that the design, as represented by the structure chart, is done before we write our program. Similarly to a architect's blueprint before building. We would not build a house without a detailed set of plans. Yet one of the most common errors of both experienced and new programmers alike is to start coding a program before the design is complete and fully documented.

This rush to start is due to the programmer's thinking they fully understand the program. In the first case, what they find is that they did not fully understand the problem. By taking time to design the program, they will raise more questions that must be answered and therefore will gain a better understanding of the problem.

Resist the temptation to code!

#6 zakmobl

Reputation: 2
• Posts: 10
• Joined: 27-February 08

Re: Dynamic Programming vs. Divide and Conquer

Posted 28 February 2009 - 09:59 AM

My understanding is that they are generally used in conjunction. If you have overlapping sub problems, you would solve them more than once unless you use dynamic programming.

Let's say for instance we wanted to multiply matrix A, B, C, D, and E. However, if not done well, you could end up with a ton more steps of multiplication.

They are associative, but not commutative. You can probably see that when solving it, various multiplication tests are done over and over again. Even though it is a divide and conquer algorithm.

Wikipedia's definition of dynamic programming might help, but its not really something you compare. Its more so divide and conquer with vs without which depends on if subproblems repeat.

A(BCDE)
Best of A is A
Best of BCDE is ...
(BC)(DE)
B(CDE)
C(DE)
CDE
(CD)E
(BCD)E
...
(BCDE)
....
(AB)(CDE)
...

#7 sokrates3D

Reputation: 0
• Posts: 9
• Joined: 26-February 08

Re: Dynamic Programming vs. Divide and Conquer

Posted 23 March 2009 - 06:57 AM

Devide and conquer is a family of algorithms that :
If you have to solve a big problem then you divide it in peaces and try to solve it with trying to solve the litle problems. The litle problems can be solved mutch faster than the big one. If the litle peaces are solved then the big problem is also solved and you just merge the peaces. (quick sort, merge sort, binary search....)

Dynamic algorithms are algorithms that remembers what the algorithm did in the past (with saving the ald calculations). So if you need for the next step the ald calculation you do not need to calculate it once again. That saves planty of execution time. Sometime the diference between a normal algorithm and an dynamik is huge. For example the calculation of Fibonaci numbers with normal algorithm and a dynamic is that the dynamic is for big values some hours quicklier than the normal one.

This post has been edited by sokrates3D: 23 March 2009 - 07:13 AM