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.
The Dynamic programming can be used when the solution to a problem can be viewed as
the result of sequence of decisions.

Example 1

Example 2

Example 3

Example 4
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 i th 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 depth first 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𝑟(𝑘) 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. ijr(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:
The element (𝑘) in the ith row and the jth column of matrix D(k) (i, j = 1, 2, . . . , n, k = 0, 1, .
𝑖⿿ÿ
. . , n) is equal to the length of the shortest path among all paths from the ith vertex to the jth
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 (𝑘)𝑖⿿ÿ= 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 thekth 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
𝑖⿿ÿ 𝑑(𝑘−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 valuesv1, . . . , 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 its smaller sub
instances. Let us consider an instance defined by the first i items, 1≤ i ≤ n, with weights w1, . .
. ,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, i.e F(i , j) = 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.

The algorithm for the knapsack problem can be stated as follows

Input: n – total items, W – capacity of the knapsack
wi– weight of the ith item, vi– value of the ith item,
Output: F(i, j) be the value of an optimal solution to this instance considering first i items
with capacity j. F(n,W) is the optimal solution
Method:
 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 back tracing 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}.

Analysis
The time efficiency and space efficiency of this algorithm are both in Θ(nW). The time
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).

AlgorithmMFKnapsack(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], Values[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-2 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 20nontrivial 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.

Figure: Example of solving an instance of the knapsack problem by the memory function algorithm

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.
Greedy method
1. Introduction to Greedy method
1.1 General method
The greedy method is the straight forward design technique applicable to variety of
applications.
The greedy approach suggests constructing a solution through a sequence of steps, each
expanding a partially constructed solution obtained so far, until a complete solution to the
problem is reached. On each step the choice made must be:

• feasible, i.e., it has to satisfy the problem’s constraints

• locally optimal, i.e., it has to be the best local choice among all feasible choices
available on that step
• irrevocable, i.e., once made, it cannot be changed on subsequent steps of the algorithm
As a rule, greedy algorithms are both intuitively appealing and simple. Given an optimization
problem, it is usually easy to figure out how to proceed in a greedy manner, possibly after
considering a few small instances of the problem. What is usually more difficult is to prove
that a greedy algorithm yields an optimal solution (when it does).
1.2. Knapsack Problem (Fractional knapsack problem)

Consider the following instance of the knapsack problem:

n=3, m=20, (p1, p2, p3) =(25, 24, 15), (w1, w2, w3) =(18, 15, 10)

There are several greedy methods to obtain the feasible solutions. Three are discussed here
a) At each step fill the knapsack with the object with largest profit - If the object under
consideration does not fit, then the fraction of it is included to fill the knapsack. This method
does not result optimal solution. As per this method the solution to the above problem is as
follows;
Select Item-1 with profit p1=25, here w1=18, x1=1. Remaining capacity = 20-18 = 2
Select Item-2 with profit p1=24, here w2=15, x1=2/15. Remaining capacity = 0 Total
profit earned = 28.2.
Therefore optimal solution is (x1, x2, x3) = (1, 2/15, 0) with profit = 28.2
b) At each step fill the object with smallest weight
Select Item-3 with profit p1=15, here w1=10, x3=1. Remaining capacity = 20-10 = 10
Select Item-2 with profit p1=24, here w2=15, x1=10/15. Remaining capacity = 0 Total
profit earned = 31.
Optimal solution using this method is (x1, x2, x3) = (0, 2/3, 1) with profit = 31
Note: Optimal solution is not guaranteed using method a and b
c) At each step include the object with maximum profit/weight ratio
Select Item-2 with profit p1=24, here w2=15, x1=1. Remaining capacity = 20-15=5
Select Item-3 with profit p1=15, here w1=10, x1=5/10. Remaining capacity = 0
Total profit earned = 31.5
Therefore, optimal solution is (x1, x2, x3) = (0, 1, 1/2) with profit = 31.5 This
greedy approach always results optimal solution.
Algorithm: The algorithm given below assumes that the objects are sorted in non-increasing
order of profit/weight ratio

Analysis:
Disregarding the time to initially sort the object, each of the above strategies use O(n) time,

0/1 Knapsack problem

Note: The greedy approach to solve 0/1 knapsack problem does not necessarily yield an optimal
solution
2. Minimum cost spanning trees
Definition: A spanning tree of a connected graph is its connected acyclic subgraph (i.e., a tree)
that contains all the vertices of the graph. A minimum spanning tree of a weighted
connected graph is its spanning tree of the smallest weight, where the weight of a tree is
defined as the sum of the weights on all its edges. The minimum spanning tree problem is
the problem of finding a minimum spanning tree for a given weighted connected graph.

2.1. Prim’s Algorithm

Prim's algorithm constructs a minimum spanning tree through a sequence of expanding sub-
trees. The initial subtree in such a sequence consists of a single vertex selected arbitrarily
from the set V of the graph's vertices. On each iteration it expands the current tree in the
greedy manner by simply attaching to it the nearest vertex not in that tree. The algorithm
stops after all the graph's vertices have been included in the tree being constructed. Since
the algorithm expands a tree by exactly one vertex on each of its iterations, the total number
of such iterations is n - 1, where n is the number of vertices in the graph. The tree generated
by the algorithm is obtained as the set of edges.

Correctness: Prim’s algorithm always yields a minimum spanning tree.

Example: An example of prim’s algorithm is shown below.
The parenthesized labels of a vertex in the middle column
indicate the nearest tree vertex and edge weight; selected
vertices and edges are shown in bold.

Tree vertices Remaining vertices Illustration

Analysis of Efficiency
The efficiency of Prim’s algorithm depends on the data structures chosen for the graph itself
and for the priority queue of the set V − VT whose vertex priorities are the distances to the
nearest tree vertices.
1. If a graph is represented by its weight matrix and the priority queue is implemented
as an unordered array, the algorithm’s running time will be in Θ(|V|2). Indeed, on
each
 of the |V| − 1iterations, the array implementing the priority queue is traversed to find and delete the
minimum and then to update, if necessary, the priorities of the remaining vertices.
We can implement the priority queue as a min-heap. (A min-heap is a complete binary tree
in which every element is less than or equal to its children.) Deletion of the smallest element
from and insertion of a new element into a min-heap of size n are O(log n) operations.
2. If a graph is represented by its adjacency lists and the priority queue is implemented
as a min-heap, the running time of the algorithm is in O(|E| log |V |).
This is because the algorithm performs |V| − 1 deletions of the smallest element and makes
|E| verifications and, possibly, changes of an element’s priority in a min-heap of size not
exceeding
|V|. Each of these operations, as noted earlier, is a O(log |V|) operation. Hence, the running
time of this implementation of Prim’s algorithm is in
(|V| − 1+ |E|) O (log |V |) = O(|E| log |V |) because, in a connected graph, |V| − 1≤ |E|.

2.2. Kruskal’s Algorithm

Background: Kruskal's algorithm is another greedy algorithm for the minimum spanning tree
problem that also always yields an optimal solution. It is named Kruskal's algorithm, after
Joseph Kruskal. Kruskal's algorithm looks at a minimum spanning tree for a weighted
connected graph G = (V, E) as an acyclic sub graph with |V | - 1 edges for which the sum of
the edge weights is the smallest. Consequently, the algorithm constructs a minimum
spanning tree as an expanding sequence of sub graphs, which are always acyclic but are not
necessarily connected on the intermediate stages of the algorithm.
Working: The algorithm begins by sorting the graph's edges in non-decreasing order of their
weights. Then, starting with the empty subgraph, it scans this sorted list adding the next
edge on the list to the current sub graph if such an inclusion does not create a cycle and
simply skipping the edge otherwise.
The fact that ET ,the set of edges composing a minimum spanning tree of graph G actually a
tree in Prim's algorithm but generally just an acyclic sub graph in Kruskal's algorithm.

Kruskal’s algorithm is not simpler because it has to check whether the addition of the next
edge to the edges already selected would create a cycle.

We can consider the algorithm's operations as a progression through a series of forests

containing all the vertices of a given graph and some of its edges. The initial forest consists of
|V| trivial trees, each comprising a single vertex of the graph. The final forest consists of a
single tree, which is a minimum spanning tree of the graph. On each iteration, the algorithm
takes the next edge (u, v) from the sorted list of the graph's edges, finds the trees containing
the vertices u and v, and, if these trees are not the same, unites them in a larger tree by
adding the edge (u, v).

Analysis of Efficiency
The crucial check whether two vertices belong to the same tree can be found out using
union-find algorithms.
Efficiency of Kruskal’s algorithm is based on the time needed for sorting the edge weights of
a given graph. Hence, with an efficient sorting algorithm, the time efficiency of Kruskal's
algorithm will be in O (|E| log |E|).

Illustration
An example of Kruskal’s algorithm is shown below. The
selected edges are shown in bold.
3. Single source shortest paths
Single-source shortest-paths problem is defined as follows. For a given vertex called the
source in a weighted connected graph, the problem is to find shortest paths to all its other
vertices. The single-source shortest-paths problem asks for a family of paths, each leading
from the source to a different vertex in the graph, though some paths may, of course, have
edges in common.

3.1. Dijkstra's Algorithm

Dijkstra's Algorithm is the best-known algorithm for the single-source shortest-paths
problem. This algorithm is applicable to undirected and directed graphs with nonnegative
weights only.
Working - Dijkstra's algorithm finds the shortest paths to a graph's vertices in order of their
distance from a given source.
▪ First, it finds the shortest path from the source to a vertex nearest to it, then to a
second nearest, and so on.
▪ In general, before its ith iteration commences, the
algorithm has already identified the shortest paths to i-1
other vertices nearest to the source. These vertices, the
source, and the edges of the shortest paths leading to
them from the source form a subtree Ti of the given graph
shown in the figure.
▪ Since all the edge weights are nonnegative, the next vertex
nearest to the source can be found among the vertices adjacent to the vertices of Ti. The
 set of vertices adjacent to the vertices in Ti can be referred to as "fringe vertices";
they are the candidates from which Dijkstra's algorithm selects the next vertex
nearest to the source.
▪ To identify the ith nearest vertex, the algorithm computes, for every fringe vertex u,
the sum of the distance to the nearest tree vertex v (given by the weight of the edge
(v, u)) and the length d., of the shortest path from the source to v (previously
determined by the algorithm) and then selects the vertex with the smallest such
sum. The fact that it suffices to compare the lengths of such special paths is the
central insight of Dijkstra's algorithm.
▪ To facilitate the algorithm's operations, we label each vertex with two labels.
o The numeric label d indicates the length of the shortest path from the source to
this vertex found by the algorithm so far; when a vertex is added to the tree, d
indicates the length of the shortest path from the source to that vertex.
o The other label indicates the name of the next-to-last vertex on such a path, i.e.,
the parent of the vertex in the tree being constructed. (It can be left unspecified
for the sources and vertices that are adjacent to none of the current tree
vertices.)
With such labeling, finding the next nearest vertex u* becomes a simple task of
finding a fringe vertex with the smallest d value. Ties can be broken arbitrarily.
▪ After we have identified a vertex u* to be added to the tree, we need to perform
two operations:
o Move u* from the fringe to the set of tree vertices.
o For each remaining fringe vertex u that is connected to u* by an edge of
weight w(u*, u) such that du*+ w(u*, u) <du, update the labels of u by u* and
du*+ w(u*, u), respectivel.

Illustration: An example of Dijkstra's algorithm is

shown below. The next closest vertex is shown in
bold. (see the figure in next page)

The shortest paths (identified by following nonnumeric labels backward from a destination
vertex in the left column to the source) and their lengths (given by numeric labels of the tree

vertices) are as follows:

The pseudocode of Dijkstra’s algorithm is given below. Note that in the following pseudocode,
VT contains a given source vertex and the fringe contains the vertices adjacent to it after
iteration 0 is completed.
Analysis:
The time efficiency of Dijkstra’s algorithm depends on the data structures used for
implementing the priority queue and for representing an input graph itself.
Efficiency is Θ(|V|2) for graphs represented by their weight matrix and the priority queue
implemented as an unordered array.
For graphs represented by their adjacency lists and the priority queue implemented as a
min-heap, it is in O (|E| log |V| )

Applications
▪ Transportation planning and packet routing in communication networks, including
the Internet
▪ Finding shortest paths in social networks, speech recognition, document formatting,
robotics, compilers, and airline crew scheduling.

4. Optimal Tree problem

Background:
Suppose we have to encode a text that comprises characters from some n-character
alphabet by assigning to each of the text's characters some sequence of bits called the
codeword. There are two types of encoding: Fixed-length encoding, Variable-length
encoding
Fixed-length encoding: This method assigns to each character a bit string of the same length
m (m >= log2n). This is exactly what the standard ASCII code does.
One way of getting a coding scheme that yields a shorter bit string on the average is based
on the old idea of assigning shorter code-words to more frequent characters and longer code-
words to less frequent characters.
Variable-length encoding: This method assigns code-words of different lengths to different
characters, introduces a problem that fixed-length encoding does not have. Namely, how
can we tell how many bits of an encoded text represent the first character? (or, more
generally, the ith) To avoid this complication, we can limit ourselves to prefix-free (or simply
prefix) codes. In a prefix ode, no code word is a prefix of a codeword of another character.
Hence, with such an encoding, we can simply scan a bit string until we get the first group of
bits that is a codeword for some character, replace these bits by this character, and repeat
this operation until the bit string's end is reached.
If we want to create a binary prefix code for some alphabet, it is natural to associate the
alphabet's characters with leaves of a binary tree in which all the left edges are labelled by 0
and all the right edges are labelled by 1 (or vice versa). The codeword of a character can
then be obtained by recording the labels on the simple path from the root to the character's
leaf. Since there is no simple path to a leaf that continues to another leaf, no codeword can
be a prefix of another codeword; hence, any such tree yields a prefix code.
Among the many trees that can be constructed in this manner for a given alphabet with
known frequencies of the character occurrences, construction of such a tree that would
assign shorter bit strings to high-frequency characters and longer ones to low-frequency
characters can be done by the following greedy algorithm, invented by David Huffman.
4.1 Huffman Trees and Codes
Huffman's Algorithm
Step 1: Initialize n one-node trees and label them with the characters of the alphabet.
Record the frequency of each character in its tree's root to indicate the tree's weight. (More
generally, the weight of a tree will be equal to the sum of the frequencies in the tree's
leaves.)
Step 2: Repeat the following operation until a single tree is obtained. Find two trees with the
smallest weight. Make them the left and right subtree of a new tree and record the sum of
their weights in the root of the new tree as its weight.
A tree constructed by the above algorithm is called a Huffmantree. It defines-in the manner
described-a Huffman code.
Example: Consider the five-symbol alphabet {A, B, C, D, _} with the following occurrence
frequencies in a text made up of
these symbols:
The Huffman tree construction
for the above problem is shown below:

The resulting codewords are as follows:

Hence, DAD is encoded as 011101, and 10011011011101 is decoded as BAD_AD.
With the occurrence frequencies given and the code word lengths obtained, the average
number of bits per symbol in this code is
2 *0.35 + 3 *0.1+ 2 *0.2 + 2 *0.2 + 3 *0.15 = 2.25.
Had we used a fixed-length encoding for the same alphabet, we would have to use at least 3
bits per each symbol. Thus, for this example, Huffman’s code achieves the compression ratio
(a standard measure of a compression algorithm’s effectiveness) of (3−2.25)/3*100%= 25%.
In other words, Huffman’s encoding of the above text will use 25% less memory than its fixed-
length encoding.