Difference between Algorithm Paradigms

Written by:

Fagun Shadi D-53

Tejas Shantaram D-71

Shruti Vasave D-76

Vidhi Raghvani D-77

Greedy Algorithmic Paradigm:

Greedy is an algorithmic paradigm that creates up an answer part by part, always choosing a subsequent part that gives the foremost obvious and immediate benefit. So, the issues where choosing locally optimal also results in global solution are best fit Greedy. A number of steps form the solution. At every step the best possible step, or solution, was selected. This process was repeated at every step till the solution was found. This is not the most optimal solution, but instead finds the best solution at every step, like a local minima. Greedy breaks the problem into sub-problems. And each sub problem is solved to the best possible way using Greedy paradigm. All sub problems are solved from the top down. The Problems are reduced step by step, and the solution is obtained when the whole problem goes away.

Dynamic Programming:

Dyanamic Programming is an optimisation on recursion algorithm. Recursive solutions have repeated calls for same inputs. This can easily be optimised by Dynamic Programming. As with every other algorithmic paradigm, every problem is broken into sub-problems. In each sub-problem, the results are stored, to reduce the number of re-computations required at each step. These Optimizations at each level, help us to save trips back to get results, and thus reduce the time complexities from exponential to polynomial. If we take the example of Fibonacci numbers, the simple recursive solution is exponential time complexity. However, we can optimise the problem by storing the solutions at each level, and thus reduce the time complexity to linear.

Divide and Conquer:

In Divide and conquer, we split the big problem into smaller sub-problems, which are identical to the big problem. That is, they are small versions of the same problem. We then find the solution for the sub-problems and then combine all the solutions to solve the bigger problem! A classic example of divide and conquer is eating a big chocolate bar. We can split the chocolate bar into smaller piece, enjoy each piece and thus eat the whole chocolate bar step by step.

Difference between the three:

Dynamic Programming solves the sub-problems bottom up. The problem can’t be solved until we find all solutions of sub-problems. The solution comes up when the whole problem appears. Greedy solves the sub-problems from top down. We first need to find the greedy choice for a problem, then reduce the problem to a smaller one. The solution is obtained when the whole problem disappears.

 Dynamic Programming has to try every possibility before solving the problem. Itis much more expensive than greedy. However, there are some problems that greedy cannot solve while dynamic programming can. Therefore, we first try greedy algorithm. If it fails, then try dynamic programming

Divide-&-conquer works best when all sub-problems are independent. So, pick partition that makes algorithm most efficient & simply combine solutions to solve entire problem.

Dynamic programming is needed when subproblems are dependent; we don’t know where to partition the problem.

Divide-&-conquer is best suited for the case when no “overlapping sub-problems” are encountered. In dynamic programming algorithms, we typically solve each subproblem only once and store their solutions. But this is at the cost of space.