Dynamic Programming.

Dynamic Programming

Definition

Dynamic programming (DP) is a general algorithm design technique for solving problems with overlapping sub-problems. This technique was invented by American mathematician “Richard Bellman” in 1950s.

Key Idea

The key idea is to save answers of overlapping smaller sub-problems to avoid re-computation.

Dynamic Programming Properties

• An instance is solved using the solutions for smaller instances.

• The solutions for a smaller instance might be needed multiple times, so store their results in a table.

• Thus each smaller instance is solved only once.

• Additional space is used to save time.

Dynamic Programming vs. Divide & Conquer

LIKE divide & conquer, dynamic programming solves problems by combining solutions to sub-problems. UNLIKE divide & conquer, sub-problems are NOT independent in dynamic programming.

Dynamic Programming vs. Divide & Conquer: EXAMPLE

Computing Fibonacci Numbers

1. Using standard recursive formula:

Algorithm F(n)

// Computes the nth Fibonacci number recursively by using its definitions

// Input: A non-negative integer n

// Output: The nth Fibonacci number

if n==0 || n==1 then

return n

else

return F(n-1) + F(n-2)

Algorithm F(n): Analysis

• Is too expensive as it has repeated calculation of smaller Fibonacci numbers.

• Exponential order of growth.

2. Using Dynamic Programming: Algorithm F(n)

// Computes the nth Fibonacci number by using dynamic programming method

// Input: A non-negative integer n

// Output: The nth Fibonacci number

Algorithm F(n): Analysis

• Since it caches previously computed values, saves time from repeated computations of same sub-instance

• Linear order of growth

Rules of Dynamic Programming

1. OPTIMAL SUB-STRUCTURE: An optimal solution to a problem contains

optimal solutions to sub-problems

2. OVERLAPPING SUB-PROBLEMS: A recursive solution contains a “small” number of distinct sub-problems repeated many times

3. BOTTOM UP FASHION: Computes the solution in a bottom-up fashion in the final step

Three basic components of Dynamic Programming solution

The development of a dynamic programming algorithm must have the following three

basic components

1. A recurrence relation

2. A tabular computation

3. A backtracking procedure

Example Problems that can be solved using Dynamic Programming method

1. Computing binomial co-efficient

2. Compute the longest common subsequence

3. Warshall’s algorithm for transitive closure

4. Floyd’s algorithm for all-pairs shortest paths

5. Some instances of difficult discrete optimization problems like

knapsack problem

traveling salesperson problem

Binomial Co-efficient

Definition:

The binomial co-efficient C(n,k) is the number of ways of choosing a subset of k elements from a set of n elements.

1. Factorial definition

For non-negative integers n & k, we have

Using DYNAMIC PROGRAMMING method: This approach stores the value of C(n,k) as they are computed i.e. Record the values of the binomial co-efficient in a table of n+1 rows and k+1 columns, numbered from 0 to n and 0 to k respectively.

Table for computing binomials is as follows:

Algorithm binomial (n, k)

// Computes C(n, k) using dynamic programming

// input: integers n≥k≥0

// output: The value of C(n, k)

Algorithm binomial (n, k): Analysis

• Input size: n, k

• Basic operation: Addition

• Let A(n, k) be the total number of additions made by the algorithm in computing C(n,k)

• The first k+1 rows of the table form a triangle while the remaining n-k rows form a rectangle. Therefore we have two parts in A(n,k).