MODULE 4

DYNAMIC PROGRAMMING

1. Introduction to Dynamic Programming

Dynamic programming is a technique for solving problems with overlapping subproblems.
Typically, these subproblems arise from a recurrence relating a given problem’s solution to
solutions of its smaller subproblems. Rather than solving overlapping subproblems again and
again, dynamic programming suggests solving each of the smaller subproblems only once
and recording the results in a table from which a solution to the original problem can then be
obtained.

It was invented by a prominent U.S. mathematician, Richard Bellman, in the 1950s as a

general method for optimizing multistage decision processes.
Dynamic programming can also be used when the solution to a problem can be viewed as
the result of sequence of decisions.

Example: Fibonacci numbers

The Fibonacci numbers are the elements of the sequence
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . ,
which can be defined by the simple recurrence
F(n) = F(n − 1) + F(n − 2) for n > 1
and two initial conditions
F(0) = 0, F(1) = 1.
Here, the problem of computing F(n) is expressed in terms of its smaller and overlapping
subproblems of computing F(n − 1) and F(n − 2). So we can simply fill elements of a one-
dimensional array with the n + 1 consecutive values of F(n) by starting, in view of initial
conditions, with 0 and 1 and using the first equation as the rule for producing all the other
elements. Obviously, the last element of this array will contain F(n).
Using Dynamic Programming,
Principle of Optimality: It is the general principle that underlines dynamic programming
applications which deals with optimization problems. It says that an optimal solution to any
instance of an optimization problem is composed of optimal solutions to its sub instances.
Basic Components of Dynamic Programming: The development of a dynamic
programming algorithm must have the following three basic components:
 A Recurrence Relation
 A tabular computation
 A Backtracking Procedure
Types of Dynamic Programming:
Classical Bottom-up Approach /Top-Down Approach

2. Transitive Closure using Warshall’s Algorithm

Definition: The transitive closure of a directed graph with n vertices can be defined as the
n× n boolean matrix T = {tij }, in which the element in the ith row and the jth column is 1 if
there exists a nontrivial path (i.e., directed path of a positive length) from the ith vertex to the jth
vertex; otherwise, tij is 0.
Example: An example of a digraph, its adjacency matrix, and its transitive closure is given
below.

(a) Digraph. (b) Its adjacency matrix. (c) Its transitive closure.

We can generate the transitive closure of a digraph with the help of depthfirst search or
breadth-first search. Performing either traversal starting at the ith vertex gives the information
about the vertices reachable from it and hence the columns that contain 1’s in the ith row of
the transitive closure. Thus, doing such a traversal for every vertex as a starting point yields
the transitive closure in its entirety.
Since this method traverses the same digraph several times, we can use a better algorithm
called Warshall’s algorithm. Warshall’s algorithm constructs the transitive closure through
a series of n × n boolean matrices:

Each of these matrices provides certain information about directed paths in the digraph.
Specifically, the element 𝑟ij(k) in the ith row and jth column of matrix R(k) (i, j = 1, 2, . . . , n, k
= 0, 1, . . . , n) is equal to 1 if and only if there exists a directed path of a positive length from
the ith vertex to the jth vertex with each intermediate vertex, if any, numbered not higher than
k.
Thus, the series starts with R(0) , which does not allow any intermediate vertices in its paths;
hence, R(0) is nothing other than the adjacency matrix of the digraph. R(1) contains the
information about paths that can use the first vertex as intermediate. The last matrix in the
series, R(n) , reflects paths that can use all n vertices of the digraph as intermediate and hence
is nothing other than the digraph’s transitive closure.
This means that there exists a path from the ith vertex vi to the jth vertex vj with each
intermediate vertex numbered not higher than k:
vi, a list of intermediate vertices each numbered not higher than k, vj . --- (*)
Two situations regarding this path are possible.

1. In the first, the list of its intermediate vertices does not contain the kth vertex. Then this
path from vi to vj has intermediate vertices numbered not higher than k−1. i.e. rij(k−1) = 1
2. The second possibility is that path (*) does contain the kth vertex vk among the
intermediate vertices. Then path (*) can be rewritten as;
vi, vertices numbered ≤ k − 1, vk, vertices numbered ≤ k − 1, vj .
i.e r(k−1) = 1 and r(k−1) = 1
ik kj

Thus, we have the following formula for generating the elements of matrix R (k) from the
elements of matrix R(k−1)

The Warshall’s algorithm works based on the above formula.

As an example, the application of Warshall’s algorithm to the digraph is shown below. New
1’s are in bold.
Analysis
Its time efficiency is Θ(n3). We can make the algorithm to run faster by treating matrix rows
as bit strings and employ the bitwise or operation available in most modern computer
languages.
Space efficiency: Although separate matrices for recording intermediate results of the
algorithm are used, that can be avoided.

3. All Pairs Shortest Paths using Floyd's Algorithm

Problem definition: Given a weighted connected graph (undirected or directed), the all-pairs
shortest paths problem asks to find the distances—i.e., the lengths of the shortest paths - from
each vertex to all other vertices.
Applications: Solution to this problem finds applications in communications, transportation
networks, and operations research. Among recent applications of the all-pairs shortest-path
problem is pre-computing distances for motion planning in computer games.
We store the lengths of shortest paths in an n x n matrix D called the distance matrix: the
element dij in the ith row and the jth column of this matrix indicates the length of the shortest
path from the ith vertex to the jth vertex.

(a) Digraph. (b) Its weight matrix. (c) Its distance matrix
We can generate the distance matrix with an algorithm that is very similar to Warshall’s
algorithm. It is called Floyd’s algorithm.
Floyd’s algorithm computes the distance matrix of a weighted graph with n vertices through a
series of n × n matrices:

(k) in the ith row and the jth column of matrix D(k) (i, j = 1, 2, . . . , n,
The element 𝑑ij k = 0, 1,
. . . , n) is equal to the length of the shortest path among all paths from the i vertex to the jth
th

vertex with each intermediate vertex, if any, numbered not higher than k.
As in Warshall’s algorithm, we can compute all the elements of each matrix D(k) from its
immediate predecessor D(k−1)

If 𝑑ij
(k) = 1, then it means that there is a path;

vi, a list of intermediate vertices each numbered not higher than k, vj .

We can partition all such paths into two disjoint subsets: those that do not use the kth vertex vk
as intermediate and those that do.
 i. Since the paths of the first subset have their intermediate vertices numbered not higher
than k − 1, the shortest of them is, by definition of our matrices, of length 𝑑ij
(k−1)

ii. In the second subset the paths are of the form

vi, vertices numbered ≤ k − 1, vk, vertices numbered ≤ k − 1, vj .

The situation is depicted symbolically in Figure, which shows

the underlying idea of Floyd’s algorithm.

Taking into account the lengths of the shortest paths in both subsets leads to the following
recurrence:

Analysis: Its time efficiency is Θ(n3), similar to the warshall’s algorithm.

 Application of Floyd’s algorithm to the digraph is shown below. Updated elements are shown
in bold.

4. Knapsack problem
We start this section with designing a dynamic programming algorithm for the knapsack
problem: given n items of known weights w1, . . . , wn and values v1, . . . , vn and a knapsack
of capacity W, find the most valuable subset of the items that fit into the knapsack.
To design a dynamic programming algorithm, we need to derive a recurrence relation that
expresses a solution to an instance of the knapsack problem in terms of solutions to it
smaller sub instances.
Let us consider an instance defined by the first i items, 1≤ i ≤ n, with weights w 1, . . . , wi,
values v1, . . . , vi , and knapsack capacity j, 1 ≤ j ≤ W. Let F(i, j) be the value of an optimal
solution to this instance. We can divide all the subsets of the first i items that fit the knapsack
of capacity j into two categories: those that do not include the ith item and those that do. Note
the following:
i. Among the subsets that do not include the ith item, the value of an optimal subset is,
by definition, F(i − 1, j).
 ii. Among the subsets that do include the ith item (hence, j − wi ≥ 0), an optimal subset is
made up of this item and an optimal subset of the first i−1 items that fits into the
knapsack of capacity j − wi . The value of such an optimal subset is vi + F(i − 1, j −
wi)
Thus, the value of an optimal solution among all feasible subsets of the first I items is the
maximum of these two values.

It is convenient to define the initial conditions as follows:

F(0, j) = 0 for j ≥ 0 and F(i, 0) = 0 for i ≥ 0.
Our goal is to find F(n, W), the maximal value of a subset of the n given items that fit into
the knapsack of capacity W, and an optimal subset itself.

Example-1: Let us consider the instance given by the following data:

The dynamic programming table, filled by applying formulas is given below

Thus, the maximal value is F(4, 5) = $37.

We can find the composition of an optimal subset by backtracing the computations of this
entry in the table:
Since F(4, 5) > F(3, 5), item 4 has to be included in an optimal solution along with an optimal
subset for filling 5 − 2 = 3 remaining units of the knapsack capacity.
The value of the latter is F(3, 3). Since F(3, 3) = F(2, 3), item 3 need not be in an optimal
subset.
Since F(2, 3) > F(1, 3), item 2 is a part of an optimal selection, which leaves element
F(1, 3 − 1) to specify its remaining composition.
Similarly, since F(1, 2) > F(0, 2), item 1 is the final part of the optimal solution {item 1,
item 2, item 4}.

Example 2: Apply Bottom up dynamic programming algorithm to the following instance of

knapsack problem. (Assume Capacity=5)

Solution:
Composition of Items in the final Optimal Solution:
Analysis
The time efficiency and space efficiency of this algorithm are both in Θ(nW). T h e
t i m e needed to find the composition of an optimal solution is in O(n).

Memory Functions
The direct top-down approach to finding a solution to such a recurrence leads to an algorithm
that solves common subproblems more than once and hence is very inefficient.
The classic dynamic programming approach, on the other hand, works bottom up: it fills a
table with solutions to all smaller subproblems, but each of them is solved only once. An
unsatisfying aspect of this approach is that solutions to some of these smaller subproblems
are often not necessary for getting a solution to the problem given. Since this drawback is not
present in the top-down approach, it is natural to try to combine the strengths of the top-down
and bottom-up approaches. The goal is to get a method that solves only subproblems that are
necessary and does so only once. Such a method exists; it is based on using memory
functions.
This method solves a given problem in the top-down manner but, in addition, maintains a
table of the kind that would have been used by a bottom-up dynamic programming algorithm.
Initially, all the table’s entries are initialized with a special “null” symbol to indicate that they
have not yet been calculated. Thereafter, whenever a new value needs to be calculated, the
method checks the corresponding entry in the table first: if this entry is not “null,” it is simply
retrieved from the table; otherwise, it is computed by the recursive call whose result is then
recorded in the table.
The following algorithm implements this idea for the knapsack problem. After initializing the
table, the recursive function needs to be called with i = n (the number of items) and j = W
(the knapsack capacity).
Algorithm MFKnapsack(i, j )
//Implements the memory function method for the knapsack problem
//Input: A nonnegative integer i indicating the number of the first items being
considered and a nonnegative integer j indicating the knapsack capacity
//Output: The value of an optimal feasible subset of the first i items
//Note: Uses as global variables input arrays Weights[1..n], V alues[1..n], and
table F[0..n, 0..W ] whose entries are initialized with −1’s except for
row 0 and column 0 initialized with 0’s
Example-3: Let us apply the memory function method to the instance considered in Example
1. The table in Figure given below gives the results. Only 11 out of 20 nontrivial values (i.e.,
not those in row 0 or in column 0) have been computed. Just one nontrivial entry, V (1, 2), is
retrieved rather than being recomputed. For larger instances, the proportion of such entries
can be significantly larger.

Example 4: Apply Memory Method function to the following instance of knapsack problem.
(Assume Capacity=5)
In general, we cannot expect more than a constant-factor gain in using the memory function
method for the knapsack problem, because its time efficiency class is the same as that of the
bottom-up algorithm.
Note: Refer Class notes for more problem

5. Limitations of Algorithm Power

A fair assessment of algorithms as problem-solving tools is inescapable: they are very
powerful instruments, especially when they are executed by modern computers. But the power
of algorithms is not unlimited. Some problems cannot be solved by any algorithm. Other
problems can be solved algorithmically but not in polynomial time. And even when a problem
can be solved in polynomial time by some algorithms, there are usually lower bounds on their
efficiency.

P, NP, and NP-Complete Problems

Deals with whether a given problem can be solved in polynomial time by some algorithm.

 Definition 1: We say that an algorithm solves a problem in polynomial time if its worst-
case time efficiency belongs to O(p(n)) where p(n) is a polynomial of the problem’s input
size n.
 Problems that can be solved in polynomial time are called tractable problems.
 Problems that cannot be solved in polynomial time are called intractable problems.
 There are several reasons for considering intractable problems:
1. We cannot solve arbitrary instances of intractable problems in a reasonable amount of
time unless such instances are very small.
2. Although there might be a huge difference between the running times in O(p(n)) for
polynomials of drastically different degrees, there are very few useful polynomial-
time algorithms with the degree of a polynomial higher than three. In addition,
polynomials that bound running times of algorithms do not usually have extremely
large coefficients.
3. Polynomial functions possess many convenient properties; in particular, both the sum
and composition of two polynomials are always polynomials too.
4. The choice of this class has led to a development of an extensive theory called
computational complexity, which seeks to classify problems according to their
inherent difficulty.
 P and NP Problems:
 Problems that can be solved in polynomial time as the set, called as P.
 Decision problems: These are problems with yes/no answers.
 Definition 2: Class P is a class of decision problems that can be solved in polynomial
time by (deterministic) algorithms. This class of problems is called polynomial (P-
problems).
 Example: searching & sorting algorithms
Finding the GCD of 2 no.s
Check whether a graph is connected or acyclic
Finding a minimum spanning tree
Finding shortest paths etc.

 There are many important problems, however, for which no polynomial-time algorithm
has been found:
Hamiltonian circuit problem Determine whether a given graph has a Hamiltonian
circuit—a path that starts and ends at the same vertex and passes through all the other
vertices exactly once.
Traveling salesman problem Find the shortest tour through n cities with known positive
integer distances between them (find the shortest Hamiltonian circuit in a complete graph
with positive integer weights).
Knapsack problem Find the most valuable subset of n items of given positive integer
weights and values that fit into a knapsack of a given positive integer capacity.
Partition problem Given n positive integers, determine whether it is possible to partition
them into two disjoint subsets with the same sum.
Bin-packing problem Given n items whose sizes are positive rational numbers not larger
than 1, put them into the smallest number of bins of size 1.
Graph-coloring problem For a given graph, find its chromatic number, which is the
smallest number of colors that need to be assigned to the graph’s vertices so that no two
adjacent vertices are assigned the same color.
Integer linear programming problem Find the maximum (or minimum) value of a linear
function of several integer-valued variables subject to a finite set of constraints in the
form of linear equalities and inequalities.

 Definition 3: A nondeterministic algorithm is a two-stage procedure that takes as its

input an instance I of a decision problem and does the following:
 Nondeterministic (“guessing”) stage: An arbitrary string S is generated that can be
thought of as a candidate solution to the given instance I.
 Deterministic (“verification”) stage: A deterministic algorithm takes both I and S as
its input and outputs yes if S represents a solution to instance I. (If S is not a solution
to instance I , the algorithm either returns no or is allowed not to halt at all.)
 A nondeterministic algorithm solves a decision problem if and only if for every yes
instance of the problem it returns yes on some execution.

 A nondeterministic algorithm is said to be nondeterministic polynomial if the time

efficiency of its verification stage is polynomial.

Definition 4: Class NP is the class of decision problems that can be solved by nondeterministic
polynomial algorithms. This class of problems is called nondeterministic polynomial.
  Most decision problems are in NP.
 Ex: Hamiltonian circuit problem, the partition problem, decision versions of the traveling
salesman, the knapsack, graph coloring, and many hundreds of other difficult
combinatorial optimization problems , the halting problem etc.

NP-Complete Problems
 An NP-complete problem is a problem in NP that is as difficult as any other problem in
this class because, by definition, any other problem in NP can be reduced to it in
polynomial time (Its notion is shown below :).


Polynomial-time reductions of NP problems to an NP-complete problem are shown

by arrows.

 Definition 5: A decision problem D1 is said to be polynomially reducible to a decision

problem D2, if there exists a function t that transforms instances of D1 to instances of D2
such that:
1. t maps all yes instances of D1 to yes instances of D2 and all no instances of D1 to no
instances of D2
2. t is computable by a polynomial time algorithm
 This implies that if a problem D1 is polynomially reducible to some problemD2 that can
be solved in polynomial time, then problem D1 can also be solved in polynomial time.

Definition 6: A decision problem D is said to be NP-complete if:

1. It belongs to class NP
2. Every problem in NP is polynomially reducible to D.
 Ex: Hamiltonian circuit problem, the partition problem, traveling salesperson problem,
graph coloring, etc.
 A decision problem can be shown as NP-complete in two steps.
Step 1. One needs to show that the problem in question is in NP; i.e., a randomly
generated string can be checked in polynomial time to determine whether or not it
represents a solution to the problem.
Step 2: it is to show that every problem in NP is reducible to the problem in question in
polynomial time. Because of the transitivity of polynomial reduction, this step can be
done by showing that a known NP-complete problem can be transformed to the problem
in question in polynomial time
 This figure illustrates proving NP-completeness by reduction
 The definition of NP-completeness immediately implies that if there exists a deterministic
polynomial-time algorithm for just one NP-complete problem, then every problem in NP
can be solved in polynomial time by a deterministic algorithm, and hence P = NP.
 In other words, finding a polynomial-time algorithm for one NP-complete problem would
mean that there is no qualitative difference between the complexity of checking a
proposed solution and finding it in polynomial time for the vast majority of decision
problems of all kinds.

NP-hard Problems:
 The optimization versions of difficult combinatorial problems fall in the class of NP-hard
problems.
 The problems that are atleast as hard as NP-complete problems are called NP-hard
problems.
 Ex: it is difficult to handle problems of combinatorial optimization such as traveling
salesman problem and knapsack problem.
 There are no known polynomial time algorithms for these.