UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

Dynamic programming – Principles of Optimality - Coin changing problem -

Warshall’s Algorithm- Floyd‘s algorithm - Optimal Binary Search Trees - Multistage
Graph - Knapsack Problem and Memory Functions - Greedy Technique – Dijkstra’s
algorithm - Huffman Trees and codes - 0/1 Knapsack problem.

Content Beyond syllabus

Optimal Merge Pattern – Computing Binomial Coefficient

 What are the differences between dynamic programming and divide

and conquer approaches? [Part A- NOV/DEC 2018]
 Show the general procedure of dynamic programming. [Part A-
APRIL/MAY 2017]

1. Dynamic Programming

Dynamic Programming was invented by Richard Bellman, 1950. It is a very general

technique for solving optimization problems.

Dynamic Programming requires:

1. Problem divided into overlapping sub-problems
2. Sub-problem can be represented by a table
3. Principle of optimality, recursive relation between smaller and larger problems
Compared to a brute force recursive algorithm that could run exponential,
the dynamic programming algorithm runs typically in quadratic time. The
recursive algorithm ran in exponential time while the iterative algorithm ran in
linear time.

Difference Between Dynamic Programming and Divide and conquer

Divide and Conquer Method Dynamic Programming

1.It deals (involves) three steps at each level of 1.It involves the sequence of four steps:
recursion: Characterize the structure of optimal
Divide the problem into a number of solutions.
subproblems. Recursively defines the values of
Conquer the subproblems by solving them optimal solutions.
recursively. Compute the value of optimal solutions
Combine the solution to the subproblems into in a Bottom-up minimum.
the solution for original subproblems. Construct an Optimal Solution from
computed information.

2. It is Recursive. 2. It is non-Recursive.

3. It does more work on subproblems and 3. It solves subproblems only once and
hence has more time consumption. then stores in the table.

4. It is a top-down approach. 4. It is a Bottom-up approach.

5. In this subproblems are independent of 5. In this subproblems are

each other. interdependent.

6. For example: Merge Sort & Binary Search 6. For example: Matrix Multiplication.
etc.

 State the principle of optimality – Part A [Apr/May 2019]

 Explain principle of Optimality?[Part A- NOV/DEC 2017]

1.1 Principles of Optimality

A problem is said to satisfy the Principle of Optimality if the sub solutions of
an optimal solution of the problem are themselves optimal solutions for their
sub problems. Examples: The shortest path problem satisfies the Principle of
Optimality.
To use dynamic programming, the problem must ob- serve the principle of
optimality, that whatever the initial state is, remaining decisions must be
optimal with regard the state following from the rest decision.
In single word it says that the Sequence of decision made at each stage

2. Coin Change Problem (or) Making change Problem using Dynamic

Programming

 Definition: A problem is said to satisfy the Principle of Optimality if the sub

solutions of an optimal solution of the problem are themselves optimal
solutions for their subproblems.
 Examples:
o The shortest path problem satisfies the Principle of Optimality.
o This is because if a,x1,x2,...,xn,b is a shortest path from node a to node b
in a graph, then the portion of xi to xj on that path is a shortest path from
xi to xj.
 o The longest path problem, on the other hand, does not satisfy the
Principle of Optimality. Take for example the undirected graph G of
nodes a, b, c, d, and e, and edges (a,b) (b,c) (c,d) (d,e) and (e,a).
o That is, G is a ring. The longest (noncyclic) path from a to d to a,b,c,d.
The sub-path from b to c on that path is simply the edge b,c. But that is
not the longest path from b to c. Rather, b,a,e,d,c is the longest path.
Thus, the subpath on a longest path is not necessarily a longest path.

Making Change Problem – What is it ?

 Making Change problem is to find change for a given amount using a

minimum number of coins from a set of denominations.
 Explanation: If we are given a set of denominations D = {d0, d1, d2, …, dn} and
if we want to change for some amount N, many combinations are possible.
Suppose {d1, d2, d5, d8}, {d0, d2, d4}, {d0, d5, d7} all feasible solutions.
 The aim of making a change is to find a solution with a minimum number of
coins / denominations. Clearly, this is an optimization problem.
 This problem can also be solved by using a greedy algorithm. However,
greedy does not ensure the minimum number of denominations.

How to Solve Making Change using Dynamic Programming?

 Conventional / greedy approach selects largest denomination first which is

not greater than remaining amount. On selecting denomination of size di in
every step, problem size keeps reducing by amount di.
 If current denomination is not possible to select then select second largest
denomination and so on. Continue this process until solution is found.
 However this approach may fail to find best solution. For example, suppose
we have denominations {1, 4, 5} and if we want change for 8, then
conventional or greedy approach returns four coins, <5, 1, 1, 1>, but optimal
solution is <4, 4>.
 Let us see how dynamic programming helps to find out the optimal solution.
 General assumption is that infinite coins are available for each denomination.
We can select any denomination any number of times.

Mathematical Formulation

 Sort all the denomination and start scanning from largest to smallest
denomination. In every iteration i, if current denomination di is acceptable,
then 1 coin is added in solution and total amount is reduced by amount di.
Hence,

C[i, j] = 1 + (c [i, j – di])

  If current denomination is larger than current problem size, then we have to
skip the denomination and stick with previously calculated solution. Hence,

C[i, j] = C[i – 1, j]

 Our objective is to find minimum number of coins, so at each step, we have to

stick with choice which returns minimum number of coin. Mathematically,
we formulate the problem as,

C[i, j] = min {C[i – 1, j] , 1 + C[i, j – di]}

Where,

di = ith denomination ,1 ≤ i ≤ n
j = Size of sub problem
C[1…..n, 0…..N] = Size of the problem
C[n, N] = Solution of the problem
n = Number of denomination
N = Amount for which change is required By combining all three cases, then

Complexity Analysis

Dynamic programming finds optimal solution by constructing table of size n x N,

where n is number of denominations and N is the amount for which we want
change. This table can be filled up in O(n.N) time, same is the space complexity.

Example Problem

Consider an instance of a problem with coins 1, 4 and 6 units. Illustrate its

solutions using dynamic programming approach involving a payment of 8
units or less.

Solution:

Optimal substructure for make a change problem,

Let us find the optimal solution for D = {d1, d2, d3} = {1, 4, 6} and N = 8. Initialize the
table C [i, 0] = 0 and C [0, j] = 0.

0 1 2 3 4 5 6 7 8

i=0 0 0 0 0 0 0 0 0 0

i=1 d1=1 0

i=2 d2=4 0

i=3 d3=6 0

Filling first column, j = 1:

C [1, 1] ⇒ i = 1, j = 1, di = d1 = 1

As, i = 1,

C [i, j] = C [1, 1] = 1 + C [i, j – di ]

= 1 + C [1, 1 – 1] = 1 + C [1, 0] = 1

C [2, 1] ⇒ i = 2, j = 1, di = d2 = 4

As, j < d2,

C [i, j] = C [2, 1] = C [i – 1, j] = C [1, 1] = 1

C [3, 1] ⇒ i = 3, j = 1, di = d3 = 6

As, j < d2,

C [3, 1] = C [i – 1, j] = C [2, 1] = 1
Filling second column, j = 2 :

C [1, 2] ⇒ i = 1, j = 2, di = d1 = 1

As, i = 1,

C [i, j] = C [1, 2] = 1 + C [1, j – di ]

= 1 + C [1, 2 – 1] = 1 + C [1, 1] = 1 + 1 = 2

C [2, 2] ⇒ i = 2, j = 2, di = d2 = 4

As, j < d2,

C [i, j] = C [2, 2] = C [i – 1, j] = C [1, 2] = 2

C [3, 2] ⇒ i = 3, j = 2, di = d3 = 6

As, j < d2,

C [i, j] = C [3, 2] = C [i – 1, j] = C [2, 2] = 2

Filling third column, j = 3:

C [1, 3] ⇒ i = 1, j = 3, di = d1 = 1

As, i = 1,

C [i, j] = 1 + C [i, j – d1 ]

= 1 + C [1, 3 – 1] = 1 + C [1, 2] = 1 + 2 = 3

C [2, 3] ⇒ i = 2, j = 3, di = d2 = 4

As, j < di,

C [i, j] = C [2, 3] = C [i – 1, j] = C [1, 3] = 3

C [3, 3] ⇒ i = 3, j = 3, di = d3 = 6

As, j < di,

C [i, j] = C [i – 1, j] = C [3, 3] = C [2, 3] = 3

Filling fourth column, j = 4 :

C [1, 4] ⇒ i = 1, j = 4, di = d1 = 1

As, i = 1,

C [i, j] = 1 + C [i, j – di]

C [1, 4] = 1 + C [1, 4 – 1] = 1 + C [1, 3] = 1 + 3 = 4

C [2, 4] ⇒ i = 2, j = 4, di = d2 = 4

As i ≠ 1 and j ≥ di

C [i, j] = min { C [i – 1, j], 1 + C [i, j – di] }

C [2, 4] = min { C [1, 4], 1 + C [2, 4 – 4] }

= min { C [1, 4], 1 + C [2, 0] } = min {4, 1 + 0} = 1

C [3, 4] ⇒ i = 3, j = 4, di = d3 = 6

As j < di,

C [i, j] = C [i – 1, j]

C [3, 4] = C [2, 4] = 1

Filling fifth column, j = 5 :

C [1, 5] ⇒ i = 1, j = 5, di = d1 = 1

As, i = 1,

C [i, j] = 1 + C [i, j – di]

= 1 + C [1, 5 – 1] = 1 + C [1, 4] = 1 + 4 = 5

C [2, 5] ⇒ i = 2, j = 5, di = d2 = 4

As i ≠ 1 and j ≥ di , So,

C [i, j] = min { C [i – 1, j], 1 + C [i, j – di] }

= min { C [1, 5], 1 + C [2, 1] } = min {5, 1 + 1} = 2

C [3, 5] ⇒ i = 3, j = 5, di = d3 = 6

As j < di,

C [i, j] = C [i – 1, j]

C [3, 5] = C [2, 5] = 2

Filling sixth column, j = 6 :

C [1, 6] ⇒ i = 1, j = 6, di = d1 = 1

As, i = 1,

C [i, j] = 1 + C [i, j – di]

= 1 + C [1, 5] = 1 + 5 = 6

C [2, 6] ⇒ i = 2, j = 6, di = d2 = 4

As i ≠ 1 and j ≥ di

C [i, j] = min { C [i – 1, j], 1 + C [i, j – di] }

= min { C [1, 6], 1 + C [2, 2] } = min {6, 1 + 2} = 3

C [3, 6] ⇒ i = 3, j = 6, di = d3 = 6

As i ≠ 1 and j ≥ di

C [i, j] = min { C [i – 1, j], 1 + C [i, j – di] }

= min { C [2, 6], 1 + C [3, 0] } = min {6, 1 + 0} = 1

Filling seventh column, j = 7 :

C [1, 7] ⇒ i = 1, j = 7, di = d1 = 1

As, i = 1,
C [i, j] = 1 + C [i, j – di]

= 1 + C [1, 6] = 1 + 6 = 7

C [2, 7] ⇒ i = 2, j = 7, di = d2 = 4

As i ≠ 1 and j ≥ di

C [i, j] = min { C [i – 1, j], 1 + C [i, j – di] }

= min { C [1, 7], 1 + C [2, 3] } = min {7, 1 + 3} = 4

C [3, 7] ⇒ i = 3, j = 7, di = d3 = 6

As i ≠ 1 and j ≥ di

C [i, j] = min { C [i – 1, j], 1 + C [i, j – di] }

= min { C [2, 7], 1 + C [3, 17] } = min {4, 2} = 2

Filling eighth column, j = 8 :

C [1, 8] ⇒ i = 1, j = 8, di = d1 = 1

As, i = 1,

C [i, j] = 1 + C [i, j – di]

= 1 + C [1, 7] = 1 + 7 = 8

C [2, 8] ⇒ i = 2, j = 8, di = d2 = 4

As i ≠ 1 and j ≥ di

C [i, j] = min { C [i – 1, j], 1 + C [i, j – di] }

= min { C [1, 8], 1 + C [2, 4] } = min {8, 1 + 1} = 2

C [3, 8] ⇒ i = 3, j = 8, di = d3 = 6

As i ≠ 1 and j ≥ di
 C [i, j] = min { C [i – 1, j], 1 + C [i, j – di] }

= min { C [2, 8], 1 + C [3, 2] } = min {2, 1 + 2} = 2

 Finally, table would look like,

0 1 2 3 4 5 6 7 8

i=0 0 0 0 0 0 0 0 0 0

i=1 d1=1 0 1 2 3 4 5 6 7 8

i=2 d2=4 0 1 2 3 1 2 3 4 2

i=3 d3=6 0 1 2 3 1 2 1 2 2

Minimum number of coins required for change of amount 8 is 2. Let us trace the
solution and find the denominations required for that.

SOLUTION:

For last cell in table, i and j would be 3 and 8 respectively.

C[n, N] = C[i, j] = C[3, 8] = 2

Step 1: (i = 3, j = 8) : C[3, 8] = 2 and C[2, 8] = 2

Here, C[i, j] = C[i – 1, j], implies nothing was added in previous solution. Algorithm
has propagated the solution of previous iteration in current iteration. So go to
previous step by reducing i. So, i = i – 1 = 3 – 1 = 2

Step 2: (i = 2, j = 8) : C[2, 8] = 2 and C[1, 8] = 8

Here, C[i, j] ≠ C[i – 1, j], implies denomination di = d2 = 4 was added in previous

solution. So add di in solution set and reduce problem size j by di.

Solution set S = {4}, j = j – di = 8 – 4 = 4.

Now we have, i = 2 and j = 4.

Step 3: (i = 2, j = 4) : C[2, 4] = 1 and C[1, 4] = 4

 Here, C[i, j] ¹ C[i – 1, j], implies denomination di = d2 = 4 was added in previous
solution. So add di in solution set and reduce problem size j by di.

Solution set S = {4, 4}, j = j – di = 4 – 4 = 0.

Problem size j is zero. So stop. We need two coins of amount 4 for optimal change of
amount 8.

 Apply warshall’s algorithm to find the transitive closure of the digraph

defined by the following adjacency matrix. [Part B- Apr/May 2018]
0100
0010
0001
0000
Prove that the time efficiency of warshall;s algorithm is cubic.
Explain why the time efficiency of warshall’s algorithm is inferior to that
of the traversal based algorithm for sparse graphs represented by their
adjacency lists.
Define minimum Spanning Tree problem?[Part A-APR/MAY 2018]
 Write the Floyd algorithm to find all pairs shortest path and derive its
time complexity. [Part B – Apr/May 2019]
 Solve the following using Floyd’s algorithm [Part B – Apr/May 2019]

3. WARSHALL’S ALGORITHM (All-Pairs Path Existence Problem)

Warshall’s and Floyd’s Algorithms: Warshall’s algorithm for computing

the transitive closure (there is a path between any two nodes) of a directed
graph and Floyd’s algorithm for the all-pairs shortest-paths problem. These
algorithms are based on dynamic programming.
 Floyd Warshall Algorithm is a method to find the shortest path between two
vertices for all the pairs of vertices.
 Apply this method to a weighted graph with no negative cycles.
 Apply some operations to the V*V matrices which initially store large
value(infinite) in each cell.
 Here we use the Dynamic Programming approach to find the shortest path
between all the possible pairs of vertices in a given graph.
 solve this problem by taking a sequence of decisions.

A directed graph (or digraph) is a graph, or set of vertices connected by

edges, where the edges have a direction associated with them.
An Adjacency matrix A = {aij} of a directed graph is the boolean matrix
that has 1 in its ithrow and jth column if and only if there is a directed edge from
the ith vertex to the jth vertex.
The transitive closure of a directed graph with n vertices can be defined
as the n x 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.

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

 The transitive closure of a digraph can be generated with the help of depth-first
search or breadth-first search. Every vertex as a starting point yields the
transitive closure for all. Warshall’s algorithm constructs the transitive closure
through a series of n × n b boolean matrices: R(0), . . . , R(k−1), R(k), . . . R(n).

 The element rij(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 tothe jth vertex with each intermediate vertex, if any,
numbered not higher than k.

Steps to compute R(0), . . . , R(k−1), R(k), . . . R(n).

 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.it may contain more 1’s than R(0).
 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.
  In general, each subsequent matrix in series has one more vertex to use as
intermediate for its paths than its predecessor.
 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.

FIGURE 2 Rule for changing zeros in Warshall’s algorithm.

 All the elements of each matrix R(k) is computed from its immediate
predecessor R(k−1). Let r (k), the element in the ith row and jth column of
matrix R(k), be equal to 1. 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.
 The first part of this representation means that there exists a path from vi
to vk with each intermediate vertex numbered not higher than k − 1 (hence, r
(k−1) = 1), and the second part means that there exists a path from vk to vj
with each intermediate vertex numbered not higher than k − 1 (hence,
rkj(k−1) = 1).
 Thus the following formula genera’s the elements of matrix R(k) from the
elements of matrix R(k−1):

Applying Warshall’s algorithm by hand:

 If an element rij is 1 in R(k−1), it remains 1 in R(k).
 If an element rij is 0 in R(k−1), it has to be changed to 1 in R(k) if and only if
the element in itsrow i and column k and the element in its column j and
row k are both 1’s in R(k−1).

Warshall’s algorithm’s time efficiency is only Θ(n3). Space efficiency is Θ(n2). i.e
matrix size.
 1’s reflect the existence of paths with
no intermediate vertices (R(0) is just
the adjacency matrix); boxed row and
column are used for getting R(1).

1’s reflect the existence of paths with

intermediate vertices numbered not
higher than 1, i.e., just vertex a (note a
new path from d to b); boxed row and
column are used for getting R(2).

1’s reflect the existence of paths with

intermediate vertices numbered not
higher than 2, i.e., a and b (note two
new paths); boxed row and column
are used for getting (3)
R .

1’s reflect the existence of paths with

intermediate vertices numbered not
higher than 3, i.e., a, b, and c (no new
paths); boxed row and column are
used for getting (4)
R .

1’s reflect the existence of paths with

intermediate vertices numbered not
higher than 4, i.e., a, b, c, and d (note
five new paths).
Figure: 3 Application of Warshall’s algorithm to the digraph shown.
New 1’s are in bold.

ALGORITHM Warshall(A[1..n, 1..n])

//ImplementsWarshall’s algorithm for computing the transitive closure

//Input: The adjacency matrix A of a digraph with n vertices
//Output: The transitive closure of the
digraphR(0) ←A
for k←1 to n do

for i ←1 to n do

for j ←1 to n do

R(k)[i, j ]←R(k−1)[i, j ] or (R(k−1)[i, k] and R(k−1)[k, j])

return R(n)
3.1. FLOYD’S ALGORITHM (All-Pairs Shortest-Paths Problem)

 Floyd’sl 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.
 Floyd’s algorithm computes the distance matrix of a weighted graph with n
vertices througha series of n × n matrices:
D(0), . . . , D(k−1), D(k), . . . , D(n)
The element dij(k) 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.

Steps to compute D(0), . . . , D(k−1), D(k), . . . , D(n)

 The series starts with D(0), which does not allow any intermediate vertices in its
paths; hence, D(0) is simply the weight matrix of the graph. As in Warshall’s
algorithm, we can compute all the elements of each matrix D(k) from its
immediate predecessor D(k−1).
 The last matrix in the series, D(n), contains the lengths of the shortest paths
among all paths that can use all n vertices as intermediate and hence is
nothing other thanthe distance matrix.
 Let dij(k) be the element in the ith row and the jth column of matrix D(k). This
means that dij(k) is equal to the length of the shortest path among all paths
from the ith vertex vi to the jth vertex vj with their intermediate vertices
numbered not higher than k.

FIGURE 4 Underlying idea of Floyd’s algorithm

 The length of the shortest path can be computed by the following recurrence:

ALGORITHM Floyd(W[1..n, 1..n])

//Implements Floyd’s algorithm for the all-pairs shortest-paths problem

//Input: The weight matrix W of a graph with no negative-length cycle
//Output: The distance matrix of the
shortest paths’ lengthsD ←W //is not
necessary if W can be overwritten
for k←1 to n do

for i ←1 to n do

for j ←1 to n do

D[i, j ]←min{D[i, j ], D[i, k]+ D[k, j]}

return D

Floyd’s Algorithm’s time efficiency is only Θ(n3). Space efficiency is Θ(n2). i.e matrix
size.
 Lengths of the shortest paths with no
intermediate vertices (D(0) is simply
theweight matrix).

Lengths of the shortest paths with

intermediate vertices numbered not
higher than 1, i.e., just a (note two new
shortest paths from b to c and from d
to c ).

Lengths of the shortest paths with

intermediate vertices numbered not
higher than 2, i.e., a and b (note a new
shortest path from c to a).

Lengths of the shortest paths with

intermediate vertices numbered not
higher than 3, i.e., a, b, and c (note four
new shortest paths from a to b, from a
to d, from b to d, and from d to b).

Lengths of the shortest paths with

intermediate vertices numbered not
higher than 4, i.e., a, b, c, and d (note a
newshortest path from c to a).

FIGURE 5 Application of Floyd’s algorithm to the digraph shown. Updated elements are
shown in bold.
Example Problem
Let the vertices of G be V = {1, 2........n} and consider a subset {1, 2........k} of vertices for some k.
For any pair of vertices i, j ∈ V, considered all paths from i to j whose intermediate vertices are
all drawn from {1, 2.......k}, and let p be a minimum weight path from amongst them.

The Floyd-Warshall algorithm exploits a link between path p and shortest paths from i to j with
all intermediate vertices in the set {1, 2.......k-1}. The link depends on whether or not k is an
intermediate vertex of path p.

If k is not an intermediate vertex of path p, then all intermediate vertices of path p are in the set
{1, 2........k-1}. Thus, the shortest path from vertex i to vertex j with all intermediate vertices in
the set {1, 2.......k-1} is also the shortest path i to j with all intermediate vertices in the set {1,
2.......k}.

If k is an intermediate vertex of path p, then we break p down into i → k → j.

Let dij(k) be the weight of the shortest path from vertex i to vertex j with all intermediate
vertices in the set {1, 2.......k}.

A recursive definition is given by

Working of Floyd Warshall Algorithm

Step-1
Make a matrix A0 which stores the information about the minimum distance of path between
the direct path for every pair of vertices. If there is no edge between two vertices, then we
initialize the distance of path in that case as infinity(very big number). See all the steps on the
bases of the above-directed graph.
Step-2
In this step, we use Ao matrix and find the shortest path via 1 as an intermediate node. Here all
the path that belongs to 1 remain unchanged in the matrix A1. Here one more thing which is
important, there is no self-loop so the diagonals are 0 always.

A1[1,1]=0, A1[2,2]=0, A1[3,3]=0, A1[4,4]=0.

A1[1,2], A1[1,3], A1[1,4], A1[2,1], A1[3,1], A1[4,1] are remain same as in matrix A0.

A1[2,3]= min(A0[2,3], A0[2,1]+A0[1,3]) = Infinity.

A1[2,4]= min(A0[2,4], A0[2,1]+A0[1,4]) = 15. Similarly find the others values. Final matrix A1 is
look like:

Step-3
In this step, we use A1 matrix and find the shortest path via 2 as an intermediate node. Here all
the path that belongs to 2 remain unchanged in the matrix A2. Here one more thing which is
important, there is no self-loop so the diagonals are 0 always.

A2[1,1]=0, A2[2,2]=0, A2[3,3]=0, A2[4,4]=0.

A2[1,2], A2[3,2], A2[4,2], A2[2,1], A2[2,3], A2[2,4] are remain same as in matrix A1.

A2[1,3]= min(A1[1,3], A1[1,2]+A1[2,3]) = 5.

A2[1,4]= min(A1[1,4], A1[1,2]+A1[2,4]) = 7. Similarly find the others values. Final matrix A2 is
look like:

Step-4
In this step, we use A2 matrix and find the shortest path via 3 as an intermediate node. Here all
the path that belongs to 3 remain unchanged in the matrix A3. Here one more thing which is
important, there is no self-loop so the diagonals are 0 always.
A3[1,1]=0, A3[2,2]=0, A3[3,3]=0, A3[4,4]=0.

A3[1,3], A3[2,3], A3[4,3], A3[3,1], A3[3,2], A3[3,4] are remain same as in matrix A2.

A3[1,2]= min(A2[1,2], A2[1,3]+A2[3,2]) = 3.

A3[1,4]= min(A2[1,4], A2[1,3]+A2[3,4]) = 6. Similarly find the others values. Final matrix A3 is
look like:

Step-5
In this step, we use A3 matrix and find the shortest path via 4 as an intermediate node. Here all
the path that belongs to 4 remain unchanged in the matrix A4. Here one more thing which is
important, there is no self-loop so the diagonals are 0 always.

A4[1,1]=0, A4[2,2]=0, A4[3,3]=0, A4[4,4]=0.

A4[1,4], A4[2,4], A4[3,4], A4[4,1], A4[4,2], A4[4,3] are remain same as in matrix A3.
A4[1,2]= min(A3[1,2], A3[1,4]+A3[4,2]) = 3.

A4[1,3]= min(A3[1,3], A3[1,4]+A3[4,3]) = 5. Similarly find the others values. Final matrix A4 is
look like:

A4 matrix is our final matrix which tells us the minimum distance between two vertices for all
the pairs of vertices.

Algorithm for Floyd Warshall Algorithm

Step:1 Create a matrix A of order N*N where N is the number of vertices.

Step:2 For i in range 1 to N:

i) For j in range 1 to N:

a) For k in range 1 to N:

A^(k)[j,k]= MIN(A^(k-1)[j,k],A^(k-1)[j,i]+A^(K-1)[i,k]).

Step:3 Print the array A.

Time Complexity

O(N*N*N) where N is the number of nodes in the given graph. Here we handle the N*N matrix N
times so for the overall operation to get the final matrix we run 3 nested loops.

Space Complexity

O(N*N) where N is the number of nodes in the given graph. We handle a matrix of order N*N to
get the final result of the algorithm.

Example II:

Apply Floyd-Warshall algorithm for constructing the shortest path. Show that matrices
D(k) and π(k) computed by the Floyd-Warshall algorithm for the graph.
Solution:

Step (i) When k = 0

Step (ii) When k =1

Step (iii) When k = 2
Step (iv) When k = 3

Step (v) When k = 4

Step (vi) When k = 5
  Outline the DP approach to solve the OBST problem and analyze its time
complexity. [Part B- Nov/Dec 2019].
 Construct the OBST for the following 5 keys with probabilities as indicated. [Part
B- Nov/Dec 2019].

i 0 1 2 3 4 5
pi 0.15 0.10 0.05 0.10 0.20
qi 0.05 0.10 0.05 0.05 0.05 0.10

4. Optimal binary Search Trees

A binary search tree is one of the most important data structures in computer
science. One of its principal applications is to implement a dictionary, a set of elements
with the operations of searching, insertion, and deletion.

FIGURE 6 Two out of 14 possible binary search trees with keys A, B, C, and D.

 Consider four keys A, B, C, and D to be searched for with probabilities 0.1, 0.2,
0.4, and 0.3, respectively. Figure 3.6 depicts two out of 14 possible binary search
trees containing these keys.
 The average number of comparisons in a successful search in the first of these
trees is 0.1 .1+ 0.2 . 2 + 0.4 . 3+ 0.3 . 4 = 2.9, and for the second one it is 0.1. 2 +
0.2 . 1+ 0.4 . 2 + 0.3 . 3= 2.1. Neither of these two trees is optimal.
The total number of binary search trees with n keys is equal to the nth Catalan number,

c(n)=(2n)!/(n+1)!n!
Let a1, . . . , an be distinct keys ordered from the smallest to the largest and let p1, . . . ,pn be
the probabilities of searching for them. Let C(i, j) be the smallest average number of
comparisons made in a successful search in a binary search tree Ti j made up of keys ai, . . .
, aj, where i, j are some integer indices, 1≤ i ≤ j ≤ n.

FIGURE 7 Binary search tree (BST) with root ak and two optimal binary search subtrees
Ti k−1 and T k+1 j

Consider all possible ways to choose a root ak among the keys ai, . . . , aj . For such a binary
search tree (Figure 7), the root contains key ak, the left subtree Ti k−1 contains keys ai, . . . ,
ak−1 optimally arranged, and the right subtree T k+1 j contains keys ak+1, . . . , aj also
optimally arranged. If we count tree levels starting with 1 to make the comparison
numbers equal the keys levels, the following recurrence relation is obtained:

We assume in above formula that C(i, i − 1) = 0 for 1≤ i ≤ n + 1, which can be interpreted

as the number of comparisons in the empty tree. Note that this formula implies that C(i,
i) = pi for 1≤ I ≤ n, as it should be for a one-node binary search tree containing ai.

FIGURE 8 Table Of The Dynamic Programming Algorithm For Constructing An

Optimal Binary Search Tree
The two-dimensional table in Figure 3.8 shows the values needed for computing
C(i, j). They are in row i and the columns to the left of column j and in column j and the
rows below row i. The arrows point to the pairs of entries whose sums are computed in
order to find the smallest one to be recorded as the value of C(i, j). This suggests filling
the table along its diagonals, starting with all zeros on the main diagonal and given
probabilities pi, 1≤ i ≤ n, right above it and moving toward the upper right corner.

ALGORITHM OptimalBST(P [1..n])

//Finds an optimal binary search tree by dynamic programming

//Input: An array P[1..n] of search probabilities for a sorted list of n keys
//Output: Average number of comparisons in successful searches in the
// optimal BST and table R of subtrees’ roots in the optimal BST
for i ←1 to n do

C[i, i −
1]←0
C[i,
i]←P[i]
R[i, i]←i
C[n + 1, n]←0
for d ←1 to n − 1 do //diagonal count

for i ←1 to n − d do

j ←i +
d
minv
al←∞
for k←i to j do

if C[i, k − 1]+ C[k + 1, j]< minval

minval←C[i, k − 1]+ C[k + 1, j]; kmin←k
R[i, j
]←kmin
sum←P[i
];
for s ←i + 1 to j do

sum←sum
+ P[s]C[i, j
]←minval + sum
return C[1, n], R

The algorithm’s space efficiency is clearly quadratic, ie, : Θ(n3); the time efficiency
of this version of the algorithm is cubic. It is Possible to reduce the running time of the
algorithm to Θ(n2) by taking advantage of monotonicity of entries in the root table, i.e.,
R[i,j] is always in the range between R[i,j-1] and R[i+1,j]

EXAMPLE: Let us illustrate the algorithm by applying it to the four-key set we

used at thebeginning of this section:
key A B C D
probability 0.1 0.2 0.4 0.3

The initial tables are:

Let us compute C(1, 2):

Thus, out of two possible binary trees containing the first two keys, A and B, the root of
the optimal tree has index 2 (i.e., it contains B), and the average number of comparisons
in a successfulsearch in this tree is 0.4.
We arrive at the following final tables:

Thus, the average number of key comparisons in the optimal tree is equal to 1.7. Since
R(1, 4) = 3, the root of the optimal tree contains the third key, i.e., C. Its left subtree is
made up of keys A and B, and its right subtree contains just key D.
To find the specific structure of these subtrees, we find first their roots by consulting the
root table again as follows. Since R(1, 2) = 2, the root of the optimal tree containing A and
B is B, with A being its left child (and the root of the one node tree: R(1, 1) = 1).
Since R(4, 4) = 4, the root of this one-node optimal tree is its only key D. Figure
3.10 presents the optimal tree in its entirety.
 FIGURE 10 Optimal Binary Search Trees for the above example

5. Multistage Graph Problem using Dynamic Programming

Multistage Graph problem is defined as follow:

 Multistage graph G = (V, E, W) is a weighted directed graph in which vertices are

partitioned into k ≥ 2 disjoint sub sets V = {V1, V2, …, Vk} such that if edge (u, v) is present in
E then u ∈ Vi and v ∈ Vi+1, 1 ≤ i ≤ k. The goal of multistage graph problem is to find
minimum cost path from source to destination vertex.
 The input to the algorithm is a k-stage graph, n vertices are indexed in increasing order of
stages.
 The algorithm operates in the backward direction, i.e. it starts from the last vertex of the
graph and proceeds in a backward direction to find minimum cost path.
 Minimum cost of vertex j ∈ Vi from vertex r ∈ Vi+1 is defined as,
Cost[j] = min{ c[j, r] + cost[r] }

where, c[j, r] is the weight of edge <j, r> and cost[r] is the cost of moving from end vertex to
vertex r.

Algorithm MULTI_STAGE (G, k, n, p)

// Description: Solve multi-stage problem using dynamic programming

// Input:
k: Number of stages in graph G = (V, E)
c[i, j]:Cost of edge (i, j)

// Output: p[1:k]:Minimum cost path

cost[n] ← 0
for j ← n – 1 to 1 do
//Let r be a vertex such that (j, r) in E and c[j, r] + cost[r] is minimum
cost[j] ← c[j, r] + cost[r]
π[j] ← r
end

//Find minimum cost path

p[1] ← 1
p[k] ← n

for j ← 2 to k - 1 do
p[j] ← π[p[j - 1]]
end
Complexity Analysis of Multistage Graph

If graph G has |E| edges, then cost computation time would be O(n + |E|). The complexity of
tracing the minimum cost path would be O(k), k < n. Thus total time complexity of multistage
graph using dynamic programming would be O(n + |E|).

Example: Find minimum path cost between vertex s and t for following multistage graph
using dynamic programming.

Solution:

Solution to multistage graph using dynamic programming is constructed as,

Cost[j] = min{c [j, r] + cost[r]}

Here, number of stages k = 5, number of vertices n = 12, source s = 1 and target t = 12

Initialization:

Cost[n] = 0 ⇒ Cost [12] = 0.

p[1] = s ⇒ p[1] = 1

p[k] = t ⇒ p[5] = 12.

r = t = 12.

Stage 4:
Stage 3:

Vertex 6 is connected to vertices 9 and 10:

Cost[6] = min{ c[6, 10] + Cost[10], c[6, 9] + Cost[9] }

= min{5 + 2, 6 + 4} = min{7, 10} = 7

p[6] = 10

Vertex 7 is connected to vertices 9 and 10:

Cost[7] = min{ c[7, 10] + Cost[10], c[7, 9] + Cost[9] }

= min{3 + 2, 4 + 4} = min{5, 8} = 5

p[7] = 10

Vertex 8 is connected to vertex 10 and 11:

Cost[8] = min{ c[8, 11] + Cost[11], c[8, 10] + Cost[10] }

= min{6 + 5, 5 + 2} = min{11, 7} = 7 p[8] = 10

Stage 2:
Vertex 2 is connected to vertices6, 7 and 8:
Cost[2] = min{ c[2, 6] + Cost[6], c[2, 7] + Cost[7], c[2, 8] + Cost[8] }

= min{4 + 7, 2 + 5, 1 + 7} = min{11, 7, 8} = 7
p[2] = 7

Vertex 3 is connected to vertices 6and 7:

Cost[3] = min{ c[3, 6] + Cost[6], c[3, 7] + Cost[7] }

= min{2 + 7, 7 + 5} = min{9, 12} = 9

p[3] = 6

Vertex 4 is connected to vertex 8:

Cost[4] = c[4, 8] + Cost[8] = 11 + 7 = 18

p[4] = 8

Vertex 5 is connected to vertices 7 and 8:

Cost[5] = min{ c[5, 7] + Cost[7], c[5, 8] + Cost[8] }

= min{11 + 5, 8 + 7} = min{16, 15} = 15 p[5] = 8

Stage 1:
Vertex 1 is connected to vertices 2, 3, 4 and 5:
Cost[1] = min{ c[1, 2] + Cost[2], c[1, 3] + Cost[3], c[1, 4] + Cost[4], c[1, 5] + Cost[5]}

= min{ 9 + 7, 7 + 9, 3 + 18, 2 + 15 }

= min { 16, 16, 21, 17 } = 16 p[1] = 2

Trace the solution:

p[1] = 2 p[2] = 7 p[7] = 10 p[10] = 12
  Explain the memory functions method for the knapsack problem and give the
algorithm.[Part B- Apr/May 2018]
 How dynamic programming is used to solve Knapsack problem. [Part A-NOV/DEC
2018]
 Solve the following instance of the 0/1 Knapsack problem given the Knapsack
capacity W=5 using dynamic programming and explain it [ Part B-APR/MAY 2017]

Items Weight Value

1 4 10
2 3 20
3 2 15

4 5 25

6. KNAPSACK PROBLEM AND MEMORY FUNCTIONS

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.
Assume that all the weights and the knapsack capacity is positive integers; the item
valuesdo not have to be integers. 0 / 1 knapsack problem means, the chosen item should
be either null or whole.
Recurrence relation that expresses a solution to an instance of the knapsack problem

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, i.e., the value of the most
valuable subset of the first i items that fit into the knapsack of capacity j.

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:

1. Among the subsets that do not include the ith item, the value of an optimal subset
is, by definition, F(i − 1, j).
2. Among the subsets that do include the ith item (hence, j – wi ≥ 0), an optimal
subset is madeup 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. Of course, if the ith item does not fit into the knapsack,
the value of an optimal subset selected from the first i items is the same as the value of an
optimal subset selected from the first i − 1 items. These observations lead to the
following recurrence:

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.

For F(i, j),compute the maximum of the entry in the previous row and the same
column andthe sum of vi and the entry in the previous row and wi columns to the left.

The table can be filled either row by row or column by column.

ALGORITHM DPKnapsack(w[1..n], v[1..n], W)

var V[0..n,0..W], P[1..n,1..W]: int

for j := 0 to W do
V[0,j] := 0
for i := 0 to n do
V[i,0] := 0
for i := 1 to n do
for j := 1 to W do
if w[i j and v[i] + V[i-1,j-w[i]] > V[i-1,j] then
 V[i,j] := v[i] + V[i-1,j-w[i]]; P[i,j] := j-w[i]
else
V[i,j] := V[i-1,j]; P[i,j] := j
return V[n,W] and the optimal subset by backtracing

Note: Running time and space: O(nW).

0/1 Knapsack problem

Here knapsack is like a container or a bag. Suppose we have given some items which have some
weights or profits. We have to put some items in the knapsack in such a way total value
produces a maximum profit.

For example, the weight of the container is 20 kg. We have to select the items in such a way that
the sum of the weight of items should be either smaller than or equal to the weight of the
container, and the profit should be maximum.

There are two types of knapsack problems:

o 0/1 knapsack problem

o Fractional knapsack problem

We will discuss both the problems one by one. First, we will learn about the 0/1 knapsack
problem.

What is the 0/1 knapsack problem?

The 0/1 knapsack problem means that the items are either completely or no items are filled in a
knapsack. For example, we have two items having weights 2kg and 3kg, respectively. If we pick
the 2kg item then we cannot pick 1kg item from the 2kg item (item is not divisible); we have to
pick the 2kg item completely. This is a 0/1 knapsack problem in which either we pick the item
completely or we will pick that item. The 0/1 knapsack problem is solved by the dynamic
programming.

What is the fractional knapsack problem?

The fractional knapsack problem means that we can divide the item. For example, we have an
item of 3 kg then we can pick the item of 2 kg and leave the item of 1 kg. The fractional
knapsack problem is solved by the Greedy approach.
Example of 0/1 knapsack problem.

Consider the problem having weights and profits are:

Weights: {3, 4, 6, 5} Profits: {2, 3, 1, 4}

The weight of the knapsack is 8 kg

The number of items is 4

The above problem can be solved by using the following method: xi = {1, 0, 0, 1}

= {0, 0, 0, 1}

= {0, 1, 0, 1}

The above are the possible combinations. 1 denotes that the item is completely picked and 0
means that no item is picked. Since there are 4 items so possible combinations will be:

24 = 16; So. There are 16 possible combinations that can be made by using the above problem.
Once all the combinations are made, we have to select the combination that provides the
maximum profit.

Another approach to solve the problem is dynamic programming approach. In dynamic

programming approach, the complicated problem is divided into sub-problems, then we find
the solution of a sub-problem and the solution of the sub-problem will be used to find the
solution of a complex problem.

How this problem can be solved by using the Dynamic programming approach?

First, create a matrix shown as below:

The rows represent the profits and weights of items. Here we have not taken the weight 8
directly, problem is divided into sub-problems, i.e., 0, 1, 2, 3, 4, 5, 6, 7, 8. The solution of the sub-
problems would be saved in the cells and answer to the problem would be stored in the final
cell.

First, we write the weights in the ascending order and profits according to their weights shown
as below:

wi = {3, 4, 5, 6}

pi = {2, 3, 4, 1}

The first row and the first column would be 0 as there is no item for w=0
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0

2 0

3 0

4 0

When i=1, W=1

w1 = 3; Since we have only one item in the set having weight 3, but the capacity of the knapsack
is 1. We cannot fill the item of 3kg in the knapsack of capacity 1 kg so add 0 at M[1][1] shown as
below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0

2 0

3 0

4 0

When i = 1, W = 2

w1 = 3; Since we have only one item in the set having weight 3, but the capacity of the knapsack
is 2. We cannot fill the item of 3kg in the knapsack of capacity 2 kg so add 0 at M[1][2] shown as
below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0

2 0

3 0

4 0
When i=1, W=3

w1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is also 3; therefore, we can fill the knapsack with an item of weight equal to 3. We put
profit corresponding to the weight 3, i.e., 2 at M[1][3] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2

2 0

3 0

4 0

When i=1, W = 4

W1= 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 4; therefore, we can fill the knapsack with an item of weight equal to 3. We put
profit corresponding to the weight 3, i.e., 2 at M[1][4] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2

2 0

3 0

4 0

When i=1, W = 5

W1= 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 5; therefore, we can fill the knapsack with an item of weight equal to 3.

We put profit corresponding to the weight 3, i.e., 2 at M[1][5] shown as below:

 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2

2 0

3 0

4 0

When i =1, W=6

W1= 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 6; therefore, we can fill the knapsack with an item of weight equal to 3.

We put profit corresponding to the weight 3, i.e., 2 at M[1][6] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2

2 0

3 0

4 0

When i=1, W = 7

W1= 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 7; therefore, we can fill the knapsack with an item of weight equal to 3.

We put profit corresponding to the weight 3, i.e., 2 at M[1][7] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2

2 0

3 0

4 0
When i =1, W =8

W1= 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 8; therefore, we can fill the knapsack with an item of weight equal to 3.

We put profit corresponding to the weight 3, i.e., 2 at M[1][8] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0

3 0

4 0

Now the value of 'i' gets incremented, and becomes 2.

When i =2, W = 1

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have only one item in the set
having weight equal to 4, and the weight of the knapsack is 1. We cannot put the item of weight
4 in a knapsack, so we add 0 at M[2][1] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0

3 0

4 0

When i =2, W = 2

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have only one item in the set
having weight equal to 4, and the weight of the knapsack is 2.

We cannot put the item of weight 4 in a knapsack, so we add 0 at M[2][2] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0

3 0

4 0

When i =2, W = 3

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set
having weights 3 and 4, and the weight of the knapsack is 3. We can put the item of weight 3 in a
knapsack, so we add 2 at M[2][3] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2

3 0

4 0

When i =2, W = 4

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set
having weights 3 and 4, and the weight of the knapsack is 4. We can put item of weight 4 in a
knapsack as the profit corresponding to weight 4 is more than the item having weight 3, so we
add 3 at M[2][4] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3

3 0

4 0
When i = 2, W = 5

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set
having weights 3 and 4, and the weight of the knapsack is 5. We can put item of weight 4 in a
knapsack and the profit corresponding to weight is 3, so we add 3 at M[2][5] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3

3 0

4 0

When i = 2, W = 6

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set
having weights 3 and 4, and the weight of the knapsack is 6. We can put item of weight 4 in a
knapsack and the profit corresponding to weight is 3, so we add 3 at M[2][6] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3

3 0

4 0

When i = 2, W = 7

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set
having weights 3 and 4, and the weight of the knapsack is 7. We can put item of weight 4 and 3
in a knapsack and the profits corresponding to weights are 2 and 3; therefore, the total profit is
5, so we add 5 at M[2][7] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 0 3 3 3 5

3 0

4 0

When i = 2, W = 8

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in the set
having weights 3 and 4, and the weight of the knapsack is 7. We can put item of weight 4 and 3
in a knapsack and the profits corresponding to weights are 2 and 3; therefore, the total profit is
5, so we add 5 at M[2][7] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0

4 0

Now the value of 'i' gets incremented, and becomes 3.

When i = 3, W = 1

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set
having weights 3, 4, and 5, and the weight of the knapsack is 1.We cannot put neither of the
items in a knapsack, so we add 0 at M[3][1] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0
4 0

When i = 3, W = 2

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set
having weight 3, 4, and 5, and the weight of the knapsack is 1. We cannot put neither of the
items in a knapsack, so we add 0 at M[3][2] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0

4 0

When i = 3, W = 3

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of
weight 3, 4, and 5 respectively and weight of the knapsack is 3. The item with a weight 3 can be
put in the knapsack and the profit corresponding to the item is 2, so we add 2 at M[3][3] shown
as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2

4 0

When i = 3, W = 4

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of
weight 3, 4, and 5 respectively, and weight of the knapsack is 4.

We can keep the item of either weight 3 or 4; the profit (3) corresponding to the weight 4 is
more than the profit corresponding to the weight 3 so we add 3 at M[3][4] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3

4 0

When i = 3, W = 5

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of
weight 3, 4, and 5 respectively, and weight of the knapsack is 5. We can keep the item of either
weight 3, 4 or 5; the profit (3) corresponding to the weight 4 is more than the profits
corresponding to the weight 3 and 5 so we add 3 at M[3][5] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3

4 0

When i =3, W = 6

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of
weight 3, 4, and 5 respectively, and weight of the knapsack is 6.

We can keep the item of either weight 3, 4 or 5; the profit (3) corresponding to the weight 4 is
more than the profits corresponding to the weight 3 and 5 so we add 3 at M[3][6] shown as
below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2
2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3

4 0

When i =3, W = 7

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of
weight 3, 4, and 5 respectively, and weight of the knapsack is 7. In this case, we can keep both
the items of weight 3 and 4, the sum of the profit would be equal to (2 + 3), i.e., 5, so we add 5 at
M[3][7] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5

4 0

When i = 3, W = 8

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items in the set of
weight 3, 4, and 5 respectively, and the weight of the knapsack is 8. In this case, we can keep
both the items of weight 3 and 4, the sum of the profit would be equal to (2 + 3), i.e., 5, so we
add 5 at M[3][8] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0

Now the value of 'i' gets incremented and becomes 4.

When i = 4, W = 1
The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of
weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 1.

The weight of all the items is more than the weight of the knapsack, so we cannot add any item
in the knapsack; Therefore, we add 0 at M[4][1] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0

When i = 4, W = 2

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of
weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 2. The weight of all the
items is more than the weight of the knapsack, so we cannot add any item in the knapsack;
Therefore, we add 0 at M[4][2] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0

When i = 4, W = 3

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of
weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 3. The item with a weight 3
can be put in the knapsack and the profit corresponding to the weight 4 is 2, so we will add 2 at
M[4][3] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2
2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2

When i = 4, W = 4

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of
weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 4. The item with a weight 4
can be put in the knapsack and the profit corresponding to the weight 4 is 3, so we will add 3 at
M[4][4] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2 3

When i = 4, W = 5

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of
weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 5. The item with a weight 4
can be put in the knapsack and the profit corresponding to the weight 4 is 3, so we will add 3 at
M[4][5] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2 3 3

When i = 4, W = 6

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of
weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 6. In this case, we can put
the items in the knapsack either of weight 3, 4, 5 or 6 but the profit, i.e., 4 corresponding to the
weight 6 is highest among all the items; therefore, we add 4 at M[4][6] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2 3 3 4

When i = 4, W = 7

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of
weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 7. Here, if we add two
items of weights 3 and 4 then it will produce the maximum profit, i.e., (2 + 3) equals to 5, so we
add 5 at M[4][7] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5

When i = 4, W = 8

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items in the set of
weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 8.

Here, if we add two items of weights 3 and 4 then it will produce the maximum profit,

i.e., (2 + 3) equals to 5, so we add 5 at M[4][8] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5

As we can observe in the above table that 5 is the maximum profit among all the entries. The
pointer points to the last row and the last column having 5 value. Now we will compare 5 value
with the previous row; if the previous row, i.e., i = 3 contains the same value 5 then the pointer
will shift upwards. Since the previous row contains the value 5 so the pointer will be shifted
upwards as shown in the below table:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5

Again, we will compare the value 5 from the above row, i.e., i = 2. Since the above row contains
the value 5 so the pointer will again be shifted upwards as shown in the below table:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5

Again, we will compare the value 5 from the above row, i.e., i = 1. Since the above row does not
contain the same value so we will consider the row i=1, and the weight corresponding to the
row is 4. Therefore, we have selected the weight 4 and we have rejected the weights 5 and 6
shown below:

x = {1, 0, 0}
The profit corresponding to the weight is 3. Therefore, the remaining profit is (5 - 3) equals to 2.
Now we will compare this value 2 with the row i = 2. Since the row (i = 1) contains the value 2;
therefore, the pointer shifted upwards shown below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5

Again we compare the value 2 with a above row, i.e., i = 1. Since the row i =0 does not contain
the value 2, so row i = 1 will be selected and the weight corresponding to the i = 1 is 3 shown
below:

X = {1, 1, 0, 0}

The profit corresponding to the weight is 2. Therefore, the remaining profit is 0. We compare 0
values with the above row. Since the above row contains a 0 value but the profit corresponding
to this row is 0. In this problem, two weights are selected, i.e., 3 and 4 to maximize the profit.
  What is greedy method? [Part A- APRIL/MAY 2017]

7.Greedy Algorithm
 The greedy method is one of the strategies like Divide and conquer used to solve
the problems. This method is used for solving optimization problems.
 An optimization problem is a problem that demands either maximum or minimum
results.
 The Greedy method is the simplest and straightforward approach. It is not an
algorithm, but it is a technique.
 The main function of this approach is that the decision is taken on the basis of the
currently available information. Whatever the current information is present, the
decision is made without worrying about the effect of the current decision in
future.
 This technique is basically used to determine the feasible solution that may or may
not be optimal.
 The feasible solution is a subset that satisfies the given criteria.
 The optimal solution is the solution which is the best and the most favorable
solution in the subset.
 In the case of feasible, if more than one solution satisfies the given criteria then
those solutions will be considered as the feasible, whereas the optimal solution is
the best solution among all the solutions.

Characteristics of Greedy method

The following are the characteristics of a greedy method:

o To construct the solution in an optimal way, this algorithm creates two sets where
one set contains all the chosen items, and another set contains the rejected items.
o A Greedy algorithm makes good local choices in the hope that the solution should
be either feasible or optimal.

Components of Greedy Algorithm

The components that can be used in the greedy algorithm are:

o Candidate set: A solution that is created from the set is known as a candidate set.
o Selection function: This function is used to choose the candidate or subset which
can be added in the solution.
o Feasibility function: A function that is used to determine whether the candidate
or subset can be used to contribute to the solution or not.
o Objective function: A function is used to assign the value to the solution or the
partial solution.
o Solution function: This function is used to intimate whether the complete
function has been reached or not.
Applications of Greedy Algorithm

o It is used in finding the shortest path.

o It is used to find the minimum spanning tree using the prim's algorithm or the
Kruskal's algorithm.
o It is used in a job sequencing with a deadline.
o This algorithm is also used to solve the fractional knapsack problem.

Pseudo code of Greedy Algorithm

Algorithm Greedy (a, n)

{
Solution : = 0;
for i = 0 to n do
{
x: = select(a);
if feasible(solution, x)
{
Solution: = union(solution , x)
}
return solution;
}}

The above is the greedy algorithm. Initially, the solution is assigned with zero value. We
pass the array and number of elements in the greedy algorithm. Inside the for loop, we
select the element one by one and checks whether the solution is feasible or not. If the
solution is feasible, then we perform the union.

Let's understand through an example.

Suppose there is a problem 'P'. I want to travel from A to B shown as below:

P:A→B

The problem is that we have to travel this journey from A to B. There are various
solutions to go from A to B. We can go from A to B by walk, car, bike, train, aeroplane,
etc. There is a constraint in the journey that we have to travel this journey within 12 hrs.
If I go by train or aeroplane then only, I can cover this distance within 12 hrs. There are
many solutions to this problem but there are only two solutions that satisfy the
constraint.

If we say that we have to cover the journey at the minimum cost. This means that we have
to travel this distance as minimum as possible, so this problem is known as a
minimization problem. Till now, we have two feasible solutions, i.e., one by train and
another one by air. Since travelling by train will lead to the minimum cost so it is an
optimal solution. An optimal solution is also the feasible solution, but providing the best
result so that solution is the optimal solution with the minimum cost. There would be
only one optimal solution.
The problem that requires either minimum or maximum result then that problem is
known as an optimization problem. Greedy method is one of the strategies used for
solving the optimization problems.

Disadvantages of using Greedy algorithm

 Greedy algorithm makes decisions based on the information available at each

phase without considering the broader problem. So, there might be a possibility
that the greedy solution does not give the best solution for every problem.
 It follows the local optimum choice at each stage with a intend of finding the global
optimum. Let's understand through an example.

Consider the graph which is given below:

We have to travel from the source to the destination at the minimum cost. Since we have
three feasible solutions having cost paths as 10, 20, and 5. 5 is the minimum cost path so
it is the optimal solution. This is the local optimum, and in this way, we find the local
optimum at each stage in order to calculate the global optimal solution.

Differences between Dynamic programming and Greedy method

Dynamic Greedy method

programming

Definition It is used to obtain the optimum It is also used to obtain the

solution. optimum solution.

Feasibility There is no special set of feasible In a greedy method, the

solutions in this method. optimum solution is obtained
from the feasible set of
solutions.

Recursion Dynamic programming considers In the greedy method, the

all the possible sequences in optimum solution is obtained
order to obtain the optimum without revising the previously
solution. generated solutions.
Principle of It guarantees that it will generate It does not guarantee that it will
optimality the optimum solution using the generate the optimum solution.
principle of optimality.

Memoization It creates the lookup table to store It is more efficient in terms of

the results of the subproblems memory as it does not create
that occupy the memory space. any table to store the previous
states.

Time Dynamic programming is slower Greedy methods are faster than

Complexity than the greedy method, like dynamic programming like
Bellman-Ford algorithm takes Dijkstra's shortest path
O(VE) time. algorithm takes (ElogV + VlogV)
time.

Method The dynamic programming uses The greedy method always

the bottom-up or top-down computes the solution in a
approach by breaking down a sequence manner, and it does
complex problem into simpler not look at the previous states.
problems.

Example 0/1 knapsack problem Fractional knapsack

 Explain how greedy approach is used in Dijkstra’s algorithm for finding the single
source shortest path for the given graph. [Part B- NOV/DEC 2018]

 Discuss Dijkstra’s Algorithm with example. [Part B NOV/DEC 2017,NOV/DEC

2018]
 Use Dijkstra’s algorithm to find the shortest path for the given graph with s as
source and t as desitnation. [Part B- NOV/DEC 2018]
7.1. Dijkstra’s Algorithm

 Dijkstra’s Algorithm solves the single-source shortest-paths problem.

 For a given vertex called the source in a weighted connected graph, find
shortest paths to allits 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.
 The most widely used applications are transportation planning and packet
routing in communication networks including the Internet.
 It also includes finding shortest paths in social networks, speech
recognition, documentformatting, robotics, compilers, and airline crew
scheduling.
 In the world of entertainment, one can mention pathfinding in video
games and findingbest solutions to puzzles using their state-space graphs.
 Dijkstra’s algorithm is the best-known algorithm for the single-source
shortest-pathsproblem.

ALGORITHM Dijkstra(G, s)

//Dijkstra’s algorithm for single-source shortest paths

//Input: A weighted connected graph G = (V, E) with nonnegative weights and
its vertex s
//Output: The length dv of a shortest path from s to v and its penultimate
vertex pv for every
// vertex v in V
Initialize(Q) //initialize priority queue to empty

for every vertex v in V

dv ← ∞; pv ← null

Insert (Q, v, dv) //initialize vertex priority in the priority queue

Ds ← 0; Decrease(Q, s, ds) //update priority of s with dsVT

←Φ

for i ←0 to |V| − 1 do

u* ← DeleteMin(Q) //delete the minimum priority element

VT ←VT 𝖴 {u* }

for every vertex u in V − VT that is

adjacent to u* doif du* + w(u*, u)
< du
 du ← du* + w(u *, u);
pu ← u*Decrease(Q,
u, du)

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. It is in Θ (|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 |).

FIGURE Application of Dijkstra’s algorithm.

The next closest vertex is shown in bold. 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:
 From a to b : a − b of
length 3 From a to d :
a − b − d of length 5
From a to c : a − b − c
of length 7
From a to e : a − b − d − e of length 9

 Write the Huffman code algorithm and derive its time complexity [Part B –
Apr/May 2019]
 Generate the Huffman code for the following data comprising of alphabet
and their frequency. a:1,b:1,cC:2, d:3, e:5, f:8,g:13,h:21 [Part B – Apr/May
2019]
 Construct the Huffman’s tree for following data and obtain its Huffman’s
code. Write the Huffman’s Algorithm.[Part B- APR/MAY 2017]

Character A B C D E -
Probability 0.5 0.35 0.5 0.1 0.4 0.2

8. Huffman Coding
The Huffman Coding Algorithm was proposed by David A. Huffman in 1950. It is
a lossless data compression mechanism. It is also known as data compression
encoding. It is widely used in image (JPEG or JPG) compression.

We know that each character is a sequence of 0's and 1's and stores using 8-bits. The
mechanism is called fixed-length encoding because each character uses the same
number of fixed-bit storage.

Here, a question ascends, is it possible to reduce the amount of space required to

store a character?

Yes, it is possible by using variable-length encoding. In this mechanism, we exploit

some characters that occur more frequently in comparison to other characters. In this
encoding technique, we can represent the same piece of text or string by reducing the
number of bits.

Huffman Encoding

Huffman encoding implements the following steps.

o It assigns a variable-length code to all the given characters.

 o The code length of a character depends on how frequently it occurs in the given
text or string.
o A character gets the smallest code if it frequently occurs.
o A character gets the largest code if it least occurs.

Huffman coding follows a prefix rule that prevents ambiguity while decoding. The rule
also ensures that the code assigned to the character is not treated as a prefix of the code
assigned to any other character.

There are the following two major steps involved in Huffman coding:

o First, construct a Huffman tree from the given input string or characters or text.
o Assign, a Huffman code to each character by traversing over the tree.

Let's brief the above two steps.

Huffman Tree

Step 1: For each character of the node, create a leaf node. The leaf node of a character
contains the frequency of that character.

Step 2: Set all the nodes in sorted order according to their frequency.

Step 3: There may exist a condition in which two nodes may have the same frequency. In
such a case, do the following:

1. Create a new internal node.

2. The frequency of the node will be the sum of the frequency of those two nodes that
have the same frequency.
3. Mark the first node as the left child and another node as the right child of the
newly created internal node.

Step 4: Repeat step 2 and 3 until all the node forms a single tree. Thus, we get a Huffman
tree.

Huffman Encoding Example

Suppose, we have to encode string abracadabra. Determine the following:

i. Huffman code for All the characters

ii. Average code length for the given String
iii. Length of the encoded string

(i) Huffman Code for All the Characters

In order to determine the code for each character, first, we construct a Huffman tree.

Step 1: Make pairs of characters and their frequencies.

(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)

Step 2: Sort pairs with respect to frequency, we get:

(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)

Step 3: Pick the first two characters and join them under a parent node.

We observe that a parent node does not have a frequency so, we must assign a frequency
to it. The parent node frequency will be the sum of its child nodes (left and right) i.e.
1+1=2.

Step 4: Repeat Steps 2 and 3 until, we get a single tree.

We observe that the pairs are already in a sorted (by step 2) manner. Again, pick the first
two pairs and join them.

We observe that a parent node does not has a frequency so, we must assign a frequency
to it. The parent node frequency will be the sum of its child nodes (left and right) i.e.
2+2=4.
Again, we check if the pairs are in a sorted manner or not. At this step, we need to sort the
pairs.

According to step 3, pick the first two pairs and join them, we get:

We observe that a parent node does not have a frequency so, we must assign a frequency
to it. The parent node frequency will be the sum of its child nodes (left and right) i.e.
2+4=6.

Again, we check if the pairs are in a sorted manner or not. At this step, we need to sort the
pairs. After sorting the tree looks like the following:
According to step 3, pick the first two pairs and join them, we get:

We observe that a parent node does not have a frequency so, we must assign a frequency
to it. The parent node frequency will be the sum of its child nodes (left and right) i.e.

5+6=11.

Therefore, we get a single tree.

At last, we will find the code for each character with the help of the above tree. Assign a
weight to each edge. Note that each left edge-weighted is 0 and the right edge-
weighted is 1.
We observe that input characters are only presented in the leave nodes and the internal
nodes have null values. In order to find the Huffman code for each character, traverse
over the Huffman tree from the root node to the leaf node of that particular character for
which we want to find code. The table describes the code and code length for each
character.

Character Frequency Code Code

Length

A 5 0 1

B 2 111 3

C 1 1100 4

D 1 1101 4

R 2 10 2

We observe that the most frequent character gets the shortest code length and the less
frequent character gets the largest code length.

Now we can encode the string (abracadabra) that we have taken above.

1. 0 111 10 0 1100 0 1101 0 111 10 0

(ii) Average Code Length for the String

The average code length of the Huffman tree can be determined by using the formula
given below:

Average Code Length = ∑ ( frequency × code length ) / ∑ ( frequency )

= { (5 x 1) + (2 x 3) + (1 x 4) + (1 x 4) + (2 x 2) } / (5+2+1+1+2)
= 2.09090909

(iii) Length of the Encoded String

The length of the encoded message can be determined by using the following formula:

length= Total number of characters in the text x Average code length per character

= 11 x 2.09090909

= 23 bits

Huffman Encoding Algorithm

Huffman (C)
n=|C|
Q=C
for i=1 to n-1
do
z=allocate_Node()
x=left[z]=Extract_Min(Q)
y=right[z]=Extract_Min(Q)
f[z]=f[x]+f[y]
Insert(Q,z)
return Extract_Min(Q)

The Huffman algorithm is a greedy algorithm. Since at every stage the algorithm looks for
the best available options.

The time complexity of the Huffman encoding is O(nlogn). Where n is the number of
characters in the given text.

Huffman Decoding

Huffman decoding is a technique that converts the encoded data into initial data. As we
have seen in encoding, the Huffman tree is made for an input string and the characters
are decoded based on their position in the tree. The decoding process is as follows:

o Start traversing over the tree from the root node and search for the character.
o If we move left in the binary tree, add 0 to the code.
o If we move right in the binary tree, add 1 to the code.

The child node holds the input character. It is assigned the code formed by subsequent 0s
and 1s. The time complexity of decoding a string is O(n), where n is the length of the
string.

8.1 HUFFMAN TREES

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 codeword.
For example, we can use a fixed- length encoding that assigns to each symbol a
bit string of the same length m (m ≥ log2 n). This is exactly what the standard
ASCII code does.
Variable-length encoding, which assigns codewords of different lengths to
different symbols, 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 (or,
more generally, the ith) symbol? To avoid this complication, we can limit
urselvesto the so-called prefix-free (or simply prefix) codes.
In a prefix code, no codeword is a prefix of a codeword of another symbol.
Hence, withsuch an encoding, we can simply scan a bit string until we get the first
group of bits that is a codeword for some symbol, replace these bits by this
symbol, and repeat this operation until the bit string’s end is reached.

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,
but see Problem 2 in this section’s exercises). 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
defines in the manner described above is called 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:
symbol A B C D _
frequency 0.35 0.1 0.2 0.2 0.15
The Huffman tree construction for this input is shown in Figure 18
 FIGURE 18 Example of constructing a Huffman coding tree

The resulting code words are as follows:

Symbol A B C D _
Frequency 0.35 0.1 0.2 0.2 0.15
Code word 11 100 00 01 101

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.

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 toy 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 text will use
25% less memory than its fixed-length encoding. Running time is O(n log n), as each
priority queue operation takes time O( log n).

Applications of Huffman’s encoding

1. Huffman’s encoding is a variable length encoding, so that number of bits

used are lesserthan fixed length encoding.
 2. Huffman’s encoding is very useful for file compression.
3. Huffman’s code is used in transmission of data in an encoded format.
4. Huffman’s encoding is used in decision trees and game playing.

 Write a Greedy algorithm to solve the 0/1 knapsack problem. Analyse its
time complexity. Show that this algorithm is not optimal with an
example.[Part B-NOV/DEC 2019]

0/1 Knapsack problem

Here knapsack is like a container or a bag. Suppose we have given some items which have
some weights or profits. We have to put some items in the knapsack in such a way total
value produces a maximum profit.

For example, the weight of the container is 20 kg. We have to select the items in such a
way that the sum of the weight of items should be either smaller than or equal to the
weight of the container, and the profit should be maximum.

There are two types of knapsack problems:

o 0/1 knapsack problem

o Fractional knapsack problem

What is the 0/1 knapsack problem?

The 0/1 knapsack problem means that the items are either completely or no items are
filled in a knapsack. For example, we have two items having weights 2kg and 3kg,
respectively. If we pick the 2kg item then we cannot pick 1kg item from the 2kg item
(item is not divisible); we have to pick the 2kg item completely. This is a 0/1 knapsack
problem in which either we pick the item completely or we will pick that item. The 0/1
knapsack problem is solved by the dynamic programming.

What is the fractional knapsack problem?

The fractional knapsack problem means that we can divide the item. For example, we
have an item of 3 kg then we can pick the item of 2 kg and leave the item of 1 kg. The
fractional knapsack problem is solved by the Greedy approach.

Binary Knapsack Problem using Greedy Algorithm

Binary knapsack problem is defined as, “Given a set of items having some
weight and value/profit associated with it. The knapsack problem is to find
the set of items such that the total weight is less than or equal to a given limit
(size of knapsack) and the total value/profit earned is as large as possible.
Knapsack problem has two variants.

 Binary or 0/1 knapsack : Item cannot be broken down into parts.

 Fractional knapsack : Item can be divided into parts.

Given a set of items, each having some weight and value/profit associated with it. The
goal is to find the set of items such that the total weight is less than or equal to a given
limit (size of knapsack) and the total value/profit earned is as large as possible.

 The knapsack is an optimization problem and it is useful in solving resource

allocation problem.
 Let X = <x1, x2, x3, . . . . . , xn> is the set of n items. W = <w1, w2, w3, . . . , wn> and V = <v1,
v2, v3, . . . , vn> are the set of weight and value associated with each items in x,
respectively. Knapsack capacity is M.
 Select items one by one from the set of items x and fill the knapsack such that it
would maximize the value. Knapsack problem has two variants. 0/1 knapsack does
not allow breaking of items. Either add entire item in a knapsack or reject it. It is also
known as a binary knapsack. Fractional knapsack allows the breaking of items. So
profit will also be considered accordingly.
 Knapsack problem can be formulated as follow :
Maximize sum_{i=1}^{n} v_i x_isumi=1nvixi subjected to sum_{i=1}^{n} w_i x_i le
Msumi=1nwixileM
x_i in (0, 1)xiin(0,1) for binary knapsack
x_i in [0, 1]xiin[0,1] for fractional knapsack
Algorithm

Algorithm to solve binary knapsack using greedy approach is described below:

Algorithm BINARY_KNAPSACK(W, V, M)
// W is an array of items
// V is an array of value or profit of items
// M is the capacity of the knapsack
// Items are pre sorted in decreasing order of pi = vi / wi ratio

S ← Φ // Variable to keep track of weight of selected items

i←1
P ← 0 // Variable to store earned profit

while S < M do
if (S + w[i]) ≤ M then
S ← Sunion ∪ w[i]
P ← P + v[i]
else
i←i+1
end
end

Examples for Binary Knapsack

Problem: Consider the following instance for the simple knapsack problem. Find
the solution using the greedy method.
N=8

P = {11, 21, 31, 33, 43, 53, 55, 65}

W = {1, 11, 21, 23, 33, 43, 45, 55}

M = 110

Solution:
Let us arrange items by decreasing order of profit density. Assume that items are labeled
as (I1, I2, I3, I4, I5, I6, I7, I8), have profit P = {11, 21, 31, 33, 43, 53, 55, 65} and weight W = {1,
11, 21, 23, 33, 43, 45, 55}.

Item Weight Value pi = vi / wi

I1 1 11 11.0

I2 11 21 1.91

I3 21 31 1.48

I4 23 33 1.44

I5 33 43 1.30

I6 43 53 1.23

I7 45 55 1.22

I8 55 65 1.18
We shall select one by one item from the above table. We check the feasibility of item, if
the inclusion of an item does not cross the knapsack capacity, then add it. Otherwise, skip
the current item and process the next. We should stop when knapsack is full or all items
are scanned

Initialize, Weight = 0, P = 0, knapsack capacity M = 110, Solution set S = { }.

Iteration 1 :
Weight = (Weight + w1) = 0 + 1 = 1
Weight ≤ M, so select I1
S = { I1 }, Weight = 1, P = 0 + 11 = 11
Iteration 2 :
Weight = (Weight + w2) = 1 + 11 = 12
Weight ≤ M, so select I2
S = { I1, I2 }, Weight = 12, P = 11 + 21 = 32
Iteration 3 :
Weight = (Weight + w3) = 12 + 21= 33
Weight ≤ M, so select I3
S = { I1, I2, I3 }, Weight = 33, P = 32 + 31 = 63
Iteration 4 :
Weight = (Weight + w4) = 33 + 23 = 56
Weight ≤ M, so select I4
S = { I1, I2, I3, I4 }, Weight = 56, P = 63 + 33 = 96
Iteration 5 :
Weight = (Weight + w5) = 56 + 33 = 89
Weight ≤ M, so select I5
S = { I1, I2, I3, I4, I5 }, Weight = 89, P = 96 + 43 = 139
Iteration 6 :
Weight = (Weight + w6) = 89 + 43 = 132
Weight > M, so reject I6
S = { I1, I2, I3, I4, I5 }, Weight = 89, P = 139
Iteration 7 :
Weight = (Weight + w7) = 89 + 45= 134
Weight > W, so reject I7
S = { I1, I2, I3, I4, I5 }, Weight = 89, P = 139
Iteration 8 : Weight = (Weight + w8) = 89 + 55= 144
Weight > M, so reject I8
S = { I1, I2, I3, I4, I5 }, Weight = 89, P = 139
All items are tested. The greedy algorithm selects items { I1, I2, I3, I4, I5 }, and gives a profit
of 139 units
Problem: Given the six items in the table below and a knapsack with weight limit
100, what is the solution to this knapsack problem?

Item ID Weight Value Value/Weight

A 100 40 0.4

B 50 35 0.7

C 40 20 0.5

D 20 4 0.2

E 10 10 1

F 10 6 0.6

Solution:
Sort the items in decreasing order of value/weight ratio.

Item ID Weight Value Value/Weight

E 10 10 1.0

B 50 35 0.7

F 10 6 0.6

C 40 20 0.5

A 100 40 0.4

D 20 4 0.2

We shall select one by one item from the above table. We check the feasibility of item, if
the inclusion of an item does not cross the knapsack capacity, we add it. Otherwise, we
skip the current item and process the next. We should stop when knapsack is full or all
items are scanned.

Initialize, Weight = 0, P = 0, knapsack capacity M = 100, Solution set S = { }.

Iteration 1 :
Weight = (Weight + WE) = 0 + 10 = 10
Weight ≤ M, so select E

S = { E }, Weight = 10, P = 0 + 10 = 10
Iteration 2 :
Weight = (Weight + WB) = 10 + 50 = 60
Weight ≤ M, so select B

S = { E, B }, Weight = 60, P = 10 + 35 = 45

Iteration 3 :
Weight = (Weight + WF) = 60 + 10 = 70
Weight ≤ M, so select F

S = { E, B, F }, Weight = 70, P = 45 + 6 = 51

Iteration 4 :
Weight = (Weight + WC) = 70 + 40 = 110
Weight > M, so reject item C

Iteration 5 :
Weight = (Weight + WA) = 70 + 100 = 170
Weight > M, so reject item A

Iteration 6 :
Weight = (Weight + WD) = 70 + 20 = 90
Weight ≤ M, so select D

S = { E, B, F, D }, Weight = 90, P = 51 + 4 = 55

All items are scanned. The greedy algorithm selects items { E, B, F, D }, and gives a profit
of 55 units.