Dynamic Programming

Module -4
 Dynamic Programming
• Dynamic Programming is a technique for solving problems with overlapping
sub-problems.

• Dynamic programming suggests solving each of the smaller sub-problems only

once and recording the results in a table from which we can obtain the
solution to the original problem.

• Dynamic programming can be interpreted as a special variety of space-and-time

tradeoff (store the results of smaller instances and solve a larger instance more
quickly rather than repeatedly solving the smaller instances more than once).
• EXAMPLE 1 Coin-rowproblem There is a row of n coins whose values are
some positive integers c1, c2, . . . , cn, not necessarily distinct. The goal is to
pick up the maximum amount of money subject to the constraint that no two
coins adjacent in the initial row can be picked up.

we have the following recurrence relation

F(n) = max{cn + F(n − 2), F(n − 1)} for n > 1,
F(0) = 0, F(1) = c1.

Example –Consider coin row of denominations 5, 1, 2, 10,6, 2.

The application of the algorithm to the coin row of denominations 5, 1, 2, 10,6, 2 is

shown in Figure 8.1.
• It yields the maximum amount of 17
• To find the coins with the maximum total value found, we need to backtrace
• the computations to see which of the two possibilities—
• In the last application of the formula, it was the sum c6 + F(4), which means
that the coin c6 = 2 is a part of an optimal solution.
• Moving to computing F(4), the maximum was produced by the sum c4 + F(2),
which means that the coin c4 = 10 is a part of an optimal solution as well.
• Finally, the maximum in computing F(2) was produced by F(1), implying that
the coin c2 is not the part of an optimal solution and the coin c1= 5 is.

• Thus, the optimal solution is {c1, c4, c6}.

C1,C4,C6 coins are selected, Maximum value is 17

• EXAMPLE 2 Change-making problem
• Give change for amount n using the minimum number of coins of
denominations d1<d2 < . . .<dm. Here, we consider a dynamic programming
algorithm for the general case, assuming availability of unlimited quantities of
coins for each of the m denominations d1< d2 < . . . < dm where d1 = 1.

we have the following recurrence for F(n):

F(i) = min {F(i − dj )} + 1 for i > 0,

F(0) = 0.
The application of the algorithm to amount n = 6 and denominations 1, 3,4
• The answer it yields is two coins. The time and space efficiencies of the
algorithm are obviously O(nm) and O(n), respectively.
• To find the coins of an optimal solution, we need to backtrace the computations
to see which of the denominations produced the minima in formula
• For the instance considered, the last application of the formula (for n = 6), the
minimum was produced by d2 = 3.
• The second minimum (for n = 6 − 3) was also produced for a coin of that
denomination. Thus, the minimum-coin set for n = 6 is two 3’s.
 EXAMPLE 3 Coin-collecting problem
• Problem Statement: Several coins are placed in cells of an n x m board, no more
than one coin per cell. A robot, located in the upper left cell of the board, needs
to collect as many of the coins as possible and bring them to the bottom right
cell. On each step, the robot can move either one cell to the right or one cell
down from its current location. When the robot visits a cell with a coin, it always
picks up that coin. Design an algorithm to find the maximum number of coins
the robot can collect and a path it needs to follow to do this.
• Solution: Let F(i, j) be the largest number of coins the robot can collect and bring
to the cell (i, j) in the ith row and jth column of the board. It can reach this cell
either from the adjacent cell (i-1, j) above it or from the adjacent cell (i, j-1) to
the left of it.
• • The largest numbers of coins that can be brought to these cells are F(i-1, j) and
Fi, j-1) respectively.
• • Hence, the largest number of coins the robot can bring to cell (i, j) is the
maximum of the two numbers F(i-1, j) and F(i, j-1), plus the one possible coin at
cell (i, j) itself.
• if F(i − 1, j) > F(i, j − 1), an optimal path to cell (i, j ) must come down from
• the adjacent cell above it;
• if F(i − 1, j) < F(i, j − 1), an optimal path to cell (i, j ) must come from the
adjacent cell on the left; and

• if F(i − 1, j) = F(i, j − 1), it can reach cell (i, j ) from either direction .
(a) Coins to collect. (b) Dynamic programming algorithm results. (c) Two
paths to collect 5 coins, the maximum number of coins possible.
 The Knapsack Problem
• To design 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.
• 0/1 knapsack problem: The 0/1 knapsack problem means that the items are
either completely or no items are filled in a knapsack.
• We assume here that all the weights and the knapsack capacity are positive
integers

15
7-7-2021 16
Solving an instance of the knapsack problem by the dynamic programming
algorithm
Solve by using Knapsack problem
The maximal value is F(4, 5) = $37.
We can find the composition of an optimal subset by back tracing (Back tracing finds the
actual optimal subset, i.e. solution), 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}
 MEMORY FUNCTION:
• The direct top-down approach to finding a solution to such a
recurrence leads to an algorithm that solves common sub
problems more than once and hence is very inefficient.
• The bottom up fills a table with solutions to all smaller sub
problems, but each of them is solved only once.
• An unsatisfying aspect of this approach is that solutions to some
of these smaller sub problems 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 sub problems 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).
 • EXAMPLE 2 Let us apply the memory function method to the
instance considered in Example 1.

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.
 Warshall’s Algorithm
• 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.
its time efficiency is only ϴ(n3).
FIGURE 8.13 Application of Warshall’s algorithm to the digraph shown. New 1’s are
in bold.
 Floyd’s Algorithms
• All-Pairs Shortest-Paths Problem:
• Floyd’s algorithm is an algorithm for finding shortest paths for all pairs in a
weighted connected graph (undirected or directed) with (+/-) edge weights.

• A distance matrix is a matrix (two-dimensional array) containing the

distances, taken pairwise, between the vertices of graph.
• The lengths of shortest paths in an n × 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.
• We can generate the distance matrix with an algorithm that is very similar
to Warshall’s algorithm is called Floyd’s algorithm.
FIGURE 8.16 Application
of Floyd’s algorithm to
the digraph shown.
Updated elements are
shown in bold.
 THE GREEDY METHOD
• Most of these problems have n inputs and require us to obtain a subset
that satisfies some constraints.
• Any subset that satisfies those constraints is called a feasible solution. We
need to find a feasible solution that either maximizes or minimizes a
given objective function.
• A feasible solution that does this is called an optimal solution

• The greedy method suggests that one can devise an algorithm that works in
stages , considering one input at a time.
• At each stage , a decision is made regarding whether a particular input is in an
optimal solution. This is done by considering the inputs in an order determined by
some selection procedure.
• If the inclusion of the next input into the partially constructed optimal solution
will result in an infeasible solution, then this input is not added to the partial
solution. Otherwise , it is added.
• The selection procedure itself is based on some optimization measure. This
version is called subset paradigm.
-
• Greedy Technique algorithms are:
– Prim’s algorithm
– Kruskal's Algorithm
– Dijkstra's Algorithm
– Huffman Tree
• A spanning tree of an undirected connected graph is its connected acyclic sub
graph (i.e., a tree) that contains all the vertices of the graph.
• If such a graph has weights assigned to its edges, a minimum spanning tree 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

• It also has a minimal cost for the sum of all edge weights in a spanning tree.

• Two algorithms used to generate spanning tree

– Prim’s Algorithm
– Kruskal’s algorithm
 Prim’s algorithm
• Prim’s algorithm is also a Greedy algorithm.

• The Prim’s algorithm is used to generate a minimum spanning tree for a

given graph.
• Prim's algorithm starts with the single node and explores all the adjacent
nodes with all the connecting edges at every step. The edges with the
minimal weights causing no cycles in the graph got selected.
 Prim’s Algorithm
• Consider the problem : given n points, connect them in the cheapest(low cost)
possible way so that there will be a path between every pair of points.

It has applications to the design of all kinds of networks— including

communication, computer, transportation, and electrical—by providing the
cheapest way to achieve connectivity.

It identifies clusters of points in data sets.

• It has been used for classification purposes in archaeology ,
biology, sociology, and other sciences

-
-
 Example

-
-
-
-
• If a graph is represented by its adjacency lists andthe
priority queue is implemented as a min-heap,the running time of the
algorithm is in 0(|E | log|V|).
• This is because the algorithm performs |V|- 1 deletions of the smallest
element and makes |E | verifications and, changes an element's priority in a
minheap of size not greater than |V|.
• Each of these operations 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 |.

-
 Kruskal's algorithm
• Kruskal’s algorithm sorts all the edges in increasing order of their edge
weights and keeps adding nodes to the tree only if the chosen edge does not
form any cycle. Also, it picks the edge with a minimum cost at first and the
edge with a maximum cost at last.

• Kruskal's algorithm looks at a minimum spanning tree for a weighted

connected graph G = (V, E) as an acyclic sub-graph with IV I - 1 edges for
which the sum of the edge weights is the smallest.
• The algorithm constructs a minimum spanning tree as an expanding sequence
of subgraphs, which are always acyclic but are not necessarily connected on
the intermediate stages of the algorithm.

-
-
 Example

-
-
-
• 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).
• There are efficient algorithms for doing so, including the crucial check
whether two vertices belong to the same tree.
• They are called union-find algorithms.
• With an efficient unionfind algorithm, the running time of Kruskal's
algorithm will be dominated by 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|).

-
 Assignment

-
 Dijkstra’s Algorithm
• The single-source shortest-paths problem: for a given vertex called the
source in a weighted connected graph, find shortest paths to all its other
vertices.
• Most widely used applications are transportation planning and packet
routing in communication networks.
• Less applications include finding shortest paths in social networks, speech
recognition, document formatting, robotics, compilers, and airline crew
scheduling.
• In the world of entertainment, one can mention path finding in video
games and finding best solutions to puzzles using their state-space graphs

-
 Working of Dijkstra’s Algorithm

-
-
-
 Example

-
-
-
• The time efficiency of algorithm
depends on the data Dijkstra's used for
implementing the prioritystructures
queue and for
representing an input graph.
• It is in Ө(| 𝑉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|)
-
 Huffman coding
• Huffman coding is a greedy approach based lossless data compression
algorithm.
• It uses variable-length encoding to compress the data.
• The main idea in Huffman coding is to assign each character with a
variable length code.
• The length of each character is decided on the basis of its occurrence
frequency.
• The character that occurred most time would have the smallest code and
the character that occurred least in the data would have the largest code.
 HUFFMAN TREES

Huffman’s algorithm
Step 1 Initialize n one-node trees and label them with the symbols of the
alphabet given. Record the frequency of each symbol 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 (ties can be broken arbitrarily). 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 Huffman tree. It creates a

Huffman code.
To encode a text that comprises symbols from some n-symbol alphabet by
assigning to each of the text’s symbols some sequence of bits called the code
word.

-
 Example

-
-
-
 Assign “0” to all left edges and “1” to all right edges.

-
Encoding Examples
DAD 011101
Decode Example
1001101101110
1 BAD_AD

-
Applications of Huffman’s encoding
• Huffman’s encoding is very useful for file compression.
• Huffman’s code is used in transmission of data in an encoded format.
• Huffman’s encoding is used in decision trees and game playing
 Character a b c d e f
Frequency 0.05 0.09 0.12 0.13 0.16 0.45