Question

Difference between divide and conquer method and greedy method in tabular form

Answer 1

hii
I'll
Divide-and-Conquer:

Strategy: Break a small problem into smaller sub-problems. Smaller sub-problems will most likely be a scaled down version of the original problem. Solve the smaller problems. Combine the smaller solutions to make the complete solution!

Example: When you want to eat a big fat chocolate. You break it into smaller pieces. And have it one at a time.

Greedy: 

Strategy: A solution is made up of a number of steps. At each step do what is best for you at that time. (Note: It may or may not be the best choice going forward into the game... Like a local maxima)

Example: When you are playing Cricket. At each ball you would want to Hit a six to maximise your score! 

 Dynamic Programming : 

Strategy: You can't just choose a local maxima always. So you would need an exhaustive search of the solution space. Instead of recomputing each step multiple times. You would calculate smaller solutions, save them in a table and look them up when recall is computationally cheaper than re-computation.

Example: Chess!.. You can't just choose the best current move. You need to think of future possibilities and scenarios.