Dynamic Programming

Dynamic Programming is a pretty powerful paradigm of solving problems. Given a problem, which can be broken down into smaller sub-problems, and these smaller sub-problems can still be broken into smaller ones - and if one manages to find out that there are some overlapping sub-problems, then its a DP problem. The problem is needed to break up into a series of overlapping sub-problems, and build up solutions to larger and larger sub-problems. The core idea of Dynamic Programming is to avoid repeated work by remembering partial results and this concept finds it application in a lot of real life situations.

In programming, Dynamic Programming is a powerful technique that allows one to solve different types of problems in time O(n2) or O(n3) for which a naive approach would take exponential time.
The following computer problems can be solved using dynamic programming approach −

  • Fibonacci number series
  • Knapsack problem
  • Tower of Hanoi
  • All pair shortest path by Floyd-Warshall
  • Shortest path by Dijkstra
  • Project scheduling

Contributor's Info

Greedy Algorithm | How to come up with a Greedy Algorithm?

Greedy Algorithm:
A greedy algorithm, as the name suggests, always makes the choice that looks best at that moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. Now the question is how to decide which choice is the best (or optimal), for that a function is required (which is called as the objective function) that needs to be optimized (either maximized or minimized) at the given point. Greedy algorithm makes greedy choices at each step such that the objective function is optimized. The Greedy Algorithm has only one shot to compute the optimal solution as it never goes back and reverses the decision.

How to come up with a Greedy Algorithm?

Let’s take an example. Suppose you are suffering from a lethal disease and you have only T years left to live. Now you want to try all the different things you always wanted to do. You are given an array A of integers denoting the time taken to complete different things in years. You want to know what is the maximum number of different things you can do in the limited time you have.

This is a simple Greedy Problem. In each iteration, one needs to greedily select the things which will take minimum time to complete and also maintain two variables currentTime and numberOfThings. So, simply sort the array A in nondecreasing order. Then, select the things one by one and add the time taken to complete that thing into currentTime and also add one to numberOfThings. Repeat as long as the currentTime is smaller than or equal to T.

Let A=[5,3,4,2,1] and T=6

After sorting, A=[1,2,3,4,5]

After 1st iteration,currentTime=1 and numberOfThings=1
After 2nd iteration, currentTime=1+2=3 and numberOfThings=2
After 3rd iteration, currentTime=3+3=6 and numberOfThings=3
After 4th iteration, currentTime=6+4=10 which is greater than T, answer will be 3.

Contributor's Info

Created: Edited: