Link not working

Since the link is not working,

go here instead-->  MNNIT-HACKER-EARTH

1. What is Dynamic Programming?

Dynamic Programming is a programming technique in which we breakdown a complex problem into smaller sub-problems.  The idea to to divide a problem into smaller sub-problems and use the solutions of these smaller sub-problems to reach to the solution of our original problem. It follows the divide-and-conquer paradigm of programming.

Where can we apply dynamic programming?

Speaking in technical terms, dynamic programming can be applied to problems have "overlapping-sub-problems" and "optimal-sub-structure". 

Now the question arises what are these terms and how does dynamic programming take advantage of that ?

Overlapping-sub-problems :
          A problem is said to have overlapping-sub-problems if the problem can be broken down into sub-problems which are reused several times.
         While following the naive approach generally, we will see that some sub-problems are generated and solved many times in our solution. So we can take advantage of this fact. We can save the answer for a sub-problem once it is calculated. The next time the same sub-problem arises, we can look up for the saved value. This technique is called "memorization".  In this way, we solve each sub-problem only once and thus reduce the number of computations.

Optimal-sub-structure :
           A problem is said to have an optimal-sub-structure if an optimal solution can be constructed effectively from the optimal solutions of its sub-problems.


This was a glimpse of Dynamic Programming. It is logical and so you will understand better by reading few examples in the next posts.

2- Rod Cutting

Rod Cutting

Problem
Assume a company buys long steel rods and cuts them into shorter rods for sale to its customers. If each cut is free and rods of different lengths can be sold for different amounts, we wish to determine how to best cut the original rods to maximize the cost.


Brute Force Solution
Let the rod be n inches long. There are 2^n-1 different ways to cut the rod.(if only integral cuts are allowed)
This can be seen by assuming that at each inch increment we have a binary decision of whether or not to make a cut. Let 0 represent no cut and 1 represent a cut.
So the number of ways to cut the rod is equal to the number of binary patterns of n-1 bits of which there are 2^n-1.
So to find the optimal value we simply add up the prices for all the pieces of each permutation and select the highest value. 

Dynamic Programming Solution
Let the cost of piece of length i has price p_i. If the optimal solution cuts the rod into k pieces of lengths i₁, i₂, ... , i_k, such that n = i₁ + i₂ + ... + i_k, then the cost for a rod of length n is

Therefore the optimal value can be found in terms of shorter rods by observing that if we make an optimal cut of length i (and the other will obviously be of length n-i) then both pieces must be optimal (and then these smaller pieces will subsequently be cut). Otherwise we could make a different cut which would produce a higher cost contradicting the assumption that the first cut was optimal.

Hence we can write the optimal cost in terms of the first cut as the maximum of either the entire rod (p_n) or the revenue from the two shorter pieces after a cut, i.e.

If we assume that we do not further cut the first piece and may cut the second part, we can rewrite the optimal substructure cost formula recursively as

 We will repeat the process for each subsequent r_n-i piece. Thus we can implement this algorithm using a simple recursive function

CUT-ROD(p,n)
1.  if n == 0
2.     return 0
3.  q = -INF
4.  for i = 1 to n
5.     q = max(q,p[i] + CUT-ROD(p,n-i)
6.  return q

The solution to this recursion can be shown to be T(n) = 2ⁿ which is exponential behavior.

The problem with this (top-down naive) solution is that we recompute all possible cuts thus producing the same run time as brute-force (only in a recursive fashion).

As discussed in the previous post, this problem has overlapping-sub-problems. So we can use memoization to reduce our computations. So we will calculate a sub-problem only for it first time and save its result. If that sub-problem is generated later as well, we will use the saved value and save computation. This approach is called Top-down DP and we will deal with it later.

 

Lets see another approach to do the same problem with DP. We can store the solutions to the smaller problems in a bottom-up manner rather than recompute them, the run time can be drastically improved (as compared to the naive solution). To implement this approach we simply solve the problems starting for smaller lengths and store these optimal revenues in an array (of size n+1). Then when evaluating longer lengths we simply look-up these values to determine the optimal cost for the larger piece. We can write it down as

In order to compute any r_j we only need the values r₀ to r_j-1 which we store in an array. Hence we will compute the new element using only previously computed values. The implementation of this approach is

BOTTOM-UP-CUT-ROD(p,n)
1.  let r[0..n] be a new array
2.  r[0] = 0
3.  for j = 1 to n
4.     q = -INF
5.     for i = 1 to j
6.        q = max(q,p[i] + r[j-i])
7.     r[j] = q
8.  return r[n]

The run time of this implementation is simply O(n²).

Thus we have reduced the run time from exponential to polynomial!


Extended Rod Cutting Algorithm

If in addition to the maximal revenue we want to know where to make the actual cuts we simply use an additional array s[] (also of size n+1) that stores the optimal cut for each segment size. Then we proceed backwards through the cuts by examining s[i] = i - s[i] starting at i = n to see where each subsequent cut is made until i = 0 (indicating that we take the last piece without further cuts). A modified implementation that explicitly performs the maximization to include s[] and print the final optimal cut lengths (which still has the same O(n²) run time) is given below

EXTENDED-BOTTOM-UP-CUT-ROD(p,n)
1.  let r[0..n] and s[0..n] be new arrays
2.  r[0] = 0
3.  for j = 1 to n
4.     q = -INF
5.     for i = 1 to j
6.        if q < p[i] + r[j-i]
7.           q = p[i] + r[j-i]
8.           s[j] = i
9.     r[j] = q
10. // Print optimal cuts
11. i = n
12. while i > 0
13.    print s[i]
14.    i = i - s[i]
15. return r and s

Example
Consider the following price table

length	0	1	2	3	4	5
pi	0	3	5	10	12	14
ri	0	/	/	/	/	/
si	/	/	/	/	/	/

Computing the r_i's with r₀ = 0
r₁:

length	0	1	2	3	4	5
pi	0	3	5	10	12	14
ri	0	3	/	/	/	/
si	/	1	/	/	/	/

r₂:

length	0	1	2	3	4	5
pi	0	3	5	10	12	14
ri	0	3	6	/	/	/
si	/	1	1	/	/	/

r₃:

length	0	1	2	3	4	5
pi	0	3	5	10	12	14
ri	0	3	6	10	/	/
si	/	1	1	3	/	/

r₄:

length	0	1	2	3	4	5
pi	0	3	5	10	12	14
ri	0	3	6	10	13	/
si	/	1	1	3	1	/

r₅:

length	0	1	2	3	4	5
pi	0	3	5	10	12	14
ri	0	3	6	10	13	16
si	/	1	1	3	1	1

Hence the maximum revenue for a rod of length 5 is 16. We can reconstruct the cuts that give this revenue from the s_i's using lines 10-14 of EXTENDED-BOTTOM-UP-CUT which gives

1 (for s₅) ⇒ i = 5 - 1 = 4
1 (for s₄) ⇒ i = 4 - 1 = 3
3 (for s₃) ⇒ i = 3 - 3 = 0

So we should make two cuts of 1 and leave the remaining 3 uncut.