ANALYSIS AND DESIGN OF

ALGORITHMS

UNIT-IV
CHAPTER 8:
DYNAMIC PROGRAMMING
 OUTLINE
 Dynamic Programming
 Computing a Binomial Coefficient
 Warshall’s Algorithm for computing the
transitive closure of a digraph
 Floyd’s Algorithm for the All-Pairs
Shortest-Paths Problem
 The Knapsack Problem
 Introduction
 Dynamic programming is an algorithm design technique
which was invented by a prominent U. S. mathematician,
Richard Bellman, in the 1950s.

 Dynamic programming is a technique for solving problems

with overlapping sub-problems.

 Typically, these sub-problems arise from a recurrence relating

a solution to a given problem with solutions to its smaller sub-
problems of the same type.

 Rather than solving overlapping sub-problems again and

again, dynamic programming suggests solving each of the
smaller sub-problems only once and recording the results in a
table from which we can then obtain a solution to the original
problem.
 Introduction
 The Fibonacci numbers are the elements of the sequence
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . ,
Which can be defined by the simple recurrence
F(n) = F(n-1) + F(n-2) for n ≥ 2
and two initial conditions, F(0) = 0, F(1) = 1.

Algorithm fib(n)
if n = 0 or n = 1 return n
return fib(n − 1) + fib(n − 2)

 If we try to use recurrence directly to compute the nth Fibonacci

number F(n) , we would have to recompute the same values of this
function many times.
 Introduction
 Notice that if we call, say, fib(5), we produce a call tree that calls
the function on the same value many different times:
fib(5)

fib(4) + fib(3)

fib(3) + fib(2) fib(2) + fib(1)

fib(2) + fib(1) fib(1) + fib(0) fib(1) + fib(0)

fib(1) + fib(0)

 In fact, we can avoid using an extra array to accomplish this task

by recording the values of just the last two elements of the
Fibonacci sequence.
 Introduction
 Dynamic programming usually takes one of two approaches:

 Bottom-up approach: All smaller subproblems of a given

problem are solved.

 Top-down approach: Avoids solving unnecessary

subproblems. This is recursion and Memory Function
combined together.
 COMPUTING A BINOMIAL COEFFICIENT

 Binomial coefficient, denoted as C(n, k) or n

, k
is the number of combinations (subsets) of k elements from
an n-element set (0 ≤ k ≤ n).

 The name “binomial coefficients” comes from the

participation of these numbers in the binomial formula:
(a + b)n = C(n, 0)an + . . . + C(n, k)an-kbk + . . . + C(n, n)bn.

 Two important properties of binomial coefficients:

 C(n, k) = C(n-1, k-1) + C(n-1, k) for n > k > 0 -------- (1)
 C(n, 0) = C(n, n) = 1 -------- (2)
 COMPUTING A BINOMIAL COEFFICIENT
 The nature of recurrence (1), which expresses the problem of
computing C(n, k) in terms of the smaller and overlapping
problems of computing C(n-1, k-1) and C(n-1, k), lends itself to
solving by the dynamic programming technique.

 To do this, we record the values of the binomial coefficients in a

table of n+1 rows and k+1 columns, numbered from 0 to n and
from 0 to k, respectively.

 To compute C(n, k), we fill the table row by row, starting with
row0 and ending with row n.

 Each row i (0 ≤ i ≤ n) is filled left to right, starting with 1 because

C(n,0) = 1.
 COMPUTING A BINOMIAL COEFFICIENT
 Row 0 through k also end with 1 on the table’s main diagonal:
C(i, i) = 1 for 0 ≤ i ≤ k.

 The other entries are computed using the formula

C(i, j) = C(i-1, j-1) + C(i-1, j)
i.e., by adding the contents of the cells in the preceding row and the
previous column and in the preceding row and the same column.
0 1 2 . . . k-1 k
0 1
1 1 1
2 1 2 1
. . . .
k 1 1
. . . .
n-1 1 C(n-1, k-1) C(n-1, k)
n 1 C(n, k)
Figure: Table for computing binomial coefficient C(n, k) by dynamic programming algorithm.
 COMPUTING A BINOMIAL COEFFICIENT
Example: Compute C(6, 3) using dynamic programming.
j
0 1 2 3
0 1
1 1 1
2 1 2 1
i 3 1 3 3 1
4 1 4 6 4
5 1 5 10 10
6 1 6 15 20

C(2, 1) = C(1,0) + C(1,1) = 1+1 = 2 C(5, 1) = C(4,0) + C(4,1) = 1+4 = 5

C(3, 1) = C(2,0) + C(2,1) = 1+2 = 3 C(5, 2) = C(4,1) + C(4,2) = 4+6 = 10
C(3, 2) = C(2,1) + C(2,2) = 2+1 = 3 C(5, 3) = C(4,2) + C(4,3) = 6+4 = 10
C(4, 1) = C(3,0) + C(3,1) = 1+3 = 4 C(6, 1) = C(5,0) + C(5,1) = 1+5 = 6
C(4, 2) = C(3,1) + C(3,2) = 3+3 = 6 C(6, 2) = C(5,1) + C(5,2) = 5+10 = 15
10
C(4, 3) = C(3,2) + C(3,3) = 3+1 = 4 C(6, 3) = C(5,2) + C(5,3) = 10+10 = 20
 COMPUTING A BINOMIAL COEFFICIENT

ALGORITHM Binomial(n, k)
//Computes C(n, k) by the dynamic programming algorithm
//Input: A pair of nonnegative integer n ≥ k ≥ 0
//Output: The value of C(n, k)
for i ← 0 to n do
for j ← 0 to min(i, k) do
if j = 0 or j = i
C[i, j] ← 1
else C[i, j] ← C[i - 1, j - 1] + C[i - 1, j]
return C[n, k]
Time Efficiency of Binomial Coefficient Algorithm
 The basic operation for this algorithm is addition.

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

computing C(n, k).

 To compute each entry by the formula, C(i, j) = C(i-1, j-1) + C(i-1, j)

requires just one addition.

 Because the first k + 1 rows of the table form a triangle while the
remaining n – k rows form a rectangle, we have to split the sum
expressing A(n, k) into two parts:
k i-1 n k k n

A(n, k) = ∑ ∑ 1 + ∑ ∑ 1 = ∑ (i-1) + ∑ k
i=1 j=1 i=k+1 j=1 i=1 i=k+1

= (k – 1)k + k (n – k) Є Θ(nk).
2
 WARSHALL’S ALGORITHM

 Warshall’s algorithm is a well-known algorithm for

computing the transitive closure (path matrix) of a directed
graph.

 Definition of a transitive closure: The transitive closure of

a directed graph with n vertices can be defined as the n-by-n
boolean matrix T = {tij}, in which the element in the ith row
(1 ≤ i ≤ n) and the jth column (1 ≤ j ≤ n) is 1 if there exists a
nontrivial directed path (i.e., a directed path of a positive
length) from the ith vertex to the jth vertex; otherwise, tij is 0.
 WARSHALL’S ALGORITHM

a b c d a b c d
a b
a 0 1 0 0 a 1 1 1 1
A= b 0 0 0 1 T= b 1 1 1 1
c d c 0 0 0 0 c 0 0 0 0
d 1 0 1 0 d 1 1 1 1

(a) Digraph. (b) Its adjacency matrix. (c) Its transitive closure.
 WARSHALL’S ALGORITHM
 We can generate the transitive closure of a digraph with the
help of depth-first search or breadth-first search.

 Performing traversal (BFS or DFS) starting at the ith vertex gives

the information about the vertices reachable from the ith vertex
and hence the columns that contain ones in the ith row of the
transitive closure.

 Thus, doing such a traversal for every vertex as a starting point

yields the transitive closure in its entirety.

 Since this method traverses the same digraph several times, we

should have a better algorithm.

 It is called Warshall’s algorithm after S. Warshall.

 WARSHALL’S ALGORITHM
 Warshall’s algorithm constructs the transitive closure of a given
digraph with n vertices through a series of n-by-n boolean
matrices:
R(0) , . . . , R(k – 1) , R(k) , . . . ,R(n) . ----------- (1)

 Each of these matrices provide certain information about directed

paths in the digraph. Specifically, the element rij(k) in the ith row
and jth column of matrix R(k) (k=0, 1, . . . ,n) is equal to 1 if and only
if there exists a directed path from the ith vertex to the jth vertex
with each intermediate vertex if any, numbered not higher than k.
 WARSHALL’S ALGORITHM

 The series starts with R(0) , which does not allow any
intermediate vertices in its path; hence, R(0) is nothing else but
the adjacency matrix of the graph.

 R(1) contains the information about paths that can use the first
vertex as intermediate; so, it may contain more ones than R(0) .

 In general, each subsequent matrix in series (1) has one more

vertex to use as intermediate for its path 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 else
but the digraph’s transitive closure.
 WARSHALL’S ALGORITHM
 We have the following formula for generating the elements of
matrix R(k) from the elements of matrix R(k-1) :
rij (k) = rij (k-1) or (rik (k-1) and rkj (k-1) ). ------------------ (3)

 This formula implies the following rule for generating elements of

matrix R(k) from elements of matrix R(k-1) :
 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 its row i and column k and the
element in its column j and row k are both 1’s in R(k-1) .

j k j k

R (k-1) = k 1 R (k) = k 1
i 0 1 i 1 1
 WARSHALL’S ALGORITHM
a b c d
a b
a 0 1 0 0 Ones reflect the existence of
paths with no intermediate
R(0) = b 0 0 0 1 vertices (R(0) is just the
adjacency matrix); boxed
c d c 0 0 0 0 row and column are used for
d 1 0 1 0 getting R(1) .

a b c d
Ones reflect the existence of
a 0 1 0 0 paths with intermediate
vertices numbered not
R(1) = b 0 0 0 1 higher than 1. i.e., just
vertex a (note a new path
c 0 0 0 0
from d to b); boxed row and
d 1 1 1 0 column are used for getting
R(2) .
Figure: Application of Warshall’s algorithm to the digraph
shown. New ones are in bold.
 WARSHALL’S ALGORITHM
a b c d
a b
a 0 1 0 1 Ones reflect the existence of
paths with intermediate
R(2) = b 0 0 0 1 vertices numbered not
c d c 0 0 0 0 higher than 2. i.e., a and b
(note two new paths); boxed
d 1 1 1 1 row and column are used for
getting R(3) .

a b c d
Ones reflect the existence of
a 0 1 0 1 paths with intermediate
vertices numbered not
R(3) = b 0 0 0 1
higher than 3. i.e., a, b and c
c 0 0 0 0 (no new paths); boxed row
and column are used for
d 1 1 1 1 getting R(4) .
Figure: Application of Warshall’s algorithm to the digraph
shown. New ones are in bold.
 WARSHALL’S ALGORITHM

a b

c d
a b c d
a 1 1 1 1 Ones reflect the existence of paths
with intermediate vertices numbered
R(4) = b 1 1 1 1 not higher than 4. i.e., a, b, c, and d
c 0 0 0 0 (note five new paths) .

d 1 1 1 1

Figure: Application of Warshall’s algorithm to the digraph

shown. New ones are in bold.
 WARSHALL’S ALGORITHM
ALGORITHM Warshall(A[1...n, 1…n])
//Implements Warshall’s algorithm for computing the
//transitive closure
//Input: The adjacency matrix A of a digraph with n vertices
//Output: The transitive closure of the digraph
R(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)
Note: The time efficiency of Warshall’s algorithm is Θ(n3)
 FLOYD’S ALGORITHM
 Given a weighted connected graph (undirected or directed), the
all-pairs shortest-paths problem asks to find the distance (lengths
of the shortest paths) from each vertex to all other vertices.

 The Distance matrix D is an n-by-n matrix in which the lengths of

shortest paths is recorded; 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 (1 ≤ i, j ≤ n).
2 a b c d a b c d
a b
6 a 0 ∞ 3 ∞ a 0 10 3 4
3 7
W= b 2 0 ∞ ∞ D= b 2 0 5 6
c 1 d c ∞ 7 0 1 c 7 7 0 1
d 6 ∞ ∞ 0 d 6 16 9 0

(a) Digraph. (b) Its weight matrix. (c) Its distance matrix.
 FLOYD’S ALGORITHM

 Floyd’s algorithm is a well-known algorithm for the all-pairs

shortest-paths problem.
 Floyd’s algorithm is named after its inventor R. Floyd.
 It is applicable to both undirected and directed weighted graphs
provided that they do not contain a cycle of a negative length.
 Floyd’s algorithm computes the distance matrix of a weighted graph
with n vertices through a series of n-by-n matrices:
D(0) , . . . , D(k – 1) , D(k) , . . . ,D(n) . ----------- (1)
 Each of these matrices contains the lengths of shortest paths with
certain constraints on the paths considered for the matrix in
question. Specifically, the element dij(k) in the ith row and jth column
of matrix D(k) (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.
 FLOYD’S ALGORITHM
 The series starts with D(0) , which does not allow any intermediate
vertices in its path; hence, D(0) is nothing but the weight matrix of the
graph.

 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 but the distance matrix being sought.

 We can compute all the elements of each matrix D(k) from its immediate
predecessor D(k-1) in series (1).
 FLOYD’S ALGORITHM
 The lengths of the shortest paths is got by the following
recurrence:
dij(k) = min { dij(k-1) , dik(k-1) + dkj(k-1) } for k ≥ 1, dij(0) = wij

dij(k-1)
Vi Vj

dik(k-1) dkj(k-1)

Vk
 FLOYD’S ALGORITHM
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’ lengths
D ← 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

Note: The time efficiency of Floyd’s algorithm is cubic i.e., Θ(n3)

 FLOYD’S ALGORITHM
2 a b c d
a b
a 0 ∞ 3 ∞ Lengths of the shortest
3 6 7 paths with no intermediate
D(0) = b 2 0 ∞ ∞ vertices (D(0) is simply the
weight matrix); boxed row
c d c ∞ 7 0 1 and column are used for
1
d 6 ∞ ∞ 0 getting D(1) .

a b c d Lengths of the shortest paths

with intermediate vertices
a 0 ∞ 3 ∞ numbered not higher than 1,
b 2 0 5 ∞ i.e., just a. (Note two new
D(1) = shortest paths from b to c
c ∞ 7 0 1 and from d to c); boxed row
and column are used for
d 6 ∞ 9 0 getting D(2) .

Figure: Application of Floyd’s algorithm to the digraph shown.

Updated elements are shown in bold.
 FLOYD’S ALGORITHM
2 a b c d
a b Lengths of the shortest
a 0 ∞ 3 ∞ paths with intermediate
3 6 7 vertices numbered not
D(2) = b 2 0 5 ∞ higher than 2, i.e., a and b.
c (Note a new shortest path
1
d c 9 7 0 1
from c to a); boxed row and
d 6 ∞ 9 0 column are used for getting
D(3) .

a b c d Lengths of the shortest

paths with intermediate
a 0 10 3 4 vertices numbered not
b 2 0 5 6 higher than 3, i.e., a, b, and
D(3) = c. (Note four new shortest
c 9 7 0 1 paths from a to b, from a to
d, from b to d, and from d
d 6 16 9 0 to b); boxed row and
column are used for
getting D(4) .
Figure: Application of Floyd’s algorithm to the digraph shown.
Updated elements are shown in bold.
 FLOYD’S ALGORITHM
2
a b
3 6 7

c d
1
a b c d
a 0 10 3 4 Lengths of the shortest paths with
b 2 0 5 6 intermediate vertices numbered
D(4) = not higher than 4, i.e., a, b, c, and
c 7 7 0 1 d. (Note a new shortest path from
c to a).
d 6 16 9 0

Figure: Application of Floyd’s algorithm to the digraph shown.

Updated elements are shown in bold.
 PRINCIPLE OF OPTIMALITY

 It is a general principle that underlines dynamic

programming algorithms for optimization problems.

 Richard Bellman called the principle as the principle of

optimality.

 It says that an optimal solution to any instance of an

optimization problem is composed of optimal solutions
to its subinstances.
 THE KNAPSACK PROBLEM

 Given a knapsack with maximum capacity W, and n

items.

 Each item i has some weight wi and value vi (all wi , vi

and W are positive integer values).

 Problem: How to pack the knapsack to achieve

maximum total value of packed items? i.e., find the
most valuable subset of the items that fit into the
knapsack.
 Knapsack problem:
a picture
Weight value
wi vi
Items

3
2
This is a knapsack 3 4
Max weight: W = 20
4 5

5 8
W = 20

9 10
 Knapsack problem
 The problem is called a “0-1 Knapsack problem“,
because each item must be entirely accepted or
rejected.
 Just another version of this problem is the “Fractional
Knapsack Problem”, where we can take fractions of
items.
 Knapsack problem: brute-force approach
 Since there are n items, there are 2n possible
combinations of items.

 We go through all combinations and find the one with

the most total value and with total weight less or equal
to W

 Running time will be O(2n)

 KNAPSACK PROBLEM
 To design a dynamic programming algorithm, we need to have a
recurrence relation that expresses a solution to an instance of the
knapsack problem in terms of solutions to its smaller sub-instances.

 The following recurrence is used for the Knapsack problem:

0 if i=0 or j=0

V[i, j] = V[i-1, j] if j-wi < 0

max{V[i-1], j], vi + V[i-1, j-wi]} if j-wi ≥ 0

Our goal is to find V[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.
 KNAPSACK PROBLEM
 Below figure illustrates the values involved in recurrence equations:
0 j-wi j W
0 0 0 0 0

i-1 0 V[i-1, j-wi] V[i-1, j]

wi , v i i 0 V[i, j]

n 0 goal
Figure: Table for solving the knapsack problem by dynamic programming.

 For i, j > 0, to compute the entry in the ith row and the jth column,
V[i, j], we compute the maximum of the entry in the previous row
and the same column and the 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.
i.e., V[i, j] = max{V[i-1], j], vi + V[i-1, j-wi]}
 Example : Let us consider the instance
given by the following data

Build a Dynamic Programming Table for this Knapsack Problem

Capacity W = 5
 Example – Dynamic Programming Table

Capacity
Item j
i 0 1 2 3 4 5
0 0 0 0 0 0 0
w1=2, v1=12 1
w2=1, v2= 10 2
w3=3, v3=20 3
w4=2, v4=15 4
Entries for Row 0:
V[0, 0]= 0 since i and j values are 0
V[0, 1]=V[0, 2]=V[0, 3]=V[0,4]=V[0, 5]=0 Since i=0
 Example – Dynamic Programming Table
Item Capacity
j

i 0 1 2 3 4 5

0 0 0 0 0 0 0
w1=2, v1=12 1 0 0 12 12 12 12
w2=1, v2= 10 2
w3=3, v3=20 3
w4=2, v4=15 4
Entries for Row 1:
V[1, 0] = 0 since j=0
V[1, 1] = V[0, 1] = 0 (Here, V[i, j]= V[i-1, j] since j-wi < 0)
V[1, 2] = max{V[0, 2], 12 + V[0, 0]} = max(0, 12) = 12
V[1, 3] = max{V[0, 3], 12 +V[0, 1]} = max(0, 12) = 12
V[1, 4] = max{V[0, 4], 12 + V[0, 2]} = max(0, 12) = 12
V[1, 5] = max{V[0, 5], 12 + V[0, 3]} = max(0, 12) = 12
 Example – Dynamic Programming Table
Item Capacity
j

i 0 1 2 3 4 5

0 0 0 0 0 0 0
w1=2, v1=12 1 0 0 12 12 12 12
w2=1, v2= 10 2 0 10 12 22 22 22
w3=3, v3= 20 3
w4=2, v4= 15 4
Entries for Row 2:
V[2, 0] = 0 since j = 0
V[2, 1] = max{V[1, 1], 10 + V[1, 0]} = max(0, 10) = 10
V[2, 2] = max{V[1, 2], 10 + V[1, 1]} = max(12, 10) = 12
V[2, 3] = max{V[1, 3], 10 +V[1, 2]} = max(12, 22) = 22
V[2, 4] = max{V[1, 4], 10 + V[1, 3]} = max(12, 22) = 22
V[2, 5] = max{V[1, 5], 10 + V[1, 4]} = max(12, 22) = 22
 Example – Dynamic Programming Table
Item Capacity
j

i 0 1 2 3 4 5

0 0 0 0 0 0 0
w1=2, v1=12 1 0 0 12 12 12 12
w2=1, v2= 10 2 0 10 12 22 22 22
w3=3, v3= 20 3 0 10 12 22 30 32
w4=2, v4= 15 4
Entries for Row 3:
V[3, 0] = 0 since j = 0
V[3, 1] = V[2, 1] = 10 (Here, V[i, j]= V[i-1, j] since j-wi < 0)
V[3, 2] = V[2, 2] = 12 (Here, V[i, j]= V[i-1, j] since j-wi < 0)
V[3, 3] = max{V[2, 3], 20 +V[2, 0]} = max(22, 20) = 22
V[3, 4] = max{V[2, 4], 20 + V[2, 1]} = max(22, 30) = 30
V[3, 5] = max{V[2, 5], 20 + V[2, 2]} = max(22, 32) = 32
 Example – Dynamic Programming Table
Item Capacity
j

i 0 1 2 3 4 5

0 0 0 0 0 0 0
w1=2, v1=12 1 0 0 12 12 12 12
w2=1, v2= 10 2 0 10 12 22 22 22
w3=3, v3= 20 3 0 10 12 22 30 32
w4=2, v4= 15 4 0 10 15 25 30 37
Entries for Row 4:
V[4, 0] = 0 since j = 0
V[4, 1] = V[3, 1] = 10 (Here, V[i, j]= V[i-1, j] since j-wi < 0)
V[4, 2] = max{V[3, 2], 15 + V[3, 0]} = max(12, 15) = 15
V[4, 3] = max{V[3, 3], 15 +V[3, 1]} = max(22, 25) = 25
V[4, 4] = max{V[3, 4], 15 + V[3, 2]} = max(30, 27) = 30
V[4, 5] = max{V[3, 5], 15 + V[3, 3]} = max(32, 37) = 37
Example: To find composition of optimal subset
Item Capacity
j

i 0 1 2 3 4 5

0 0 0 0 0 0 0
w1=2, v1=12 1 0 0 12 12 12 12
w2=1, v2= 10 2 0 10 12 22 22 22
w3=3, v3= 20 3 0 10 12 22 30 32
w4=2, v4= 15 4 0 10 15 25 30 37
 Thus, the maximal value is V [4, 5]= $37. We can find the composition
of an optimal subset by tracing back the computations of this entry in
the table.

 Since V [4, 5] is not equal to V [3, 5], item 4 was included in an optimal
solution along with an optimal subset for filling 5 - 2 = 3 remaining
units of the knapsack capacity.
Example: To find composition of optimal subset

Item Capacity
j

i 0 1 2 3 4 5

0 0 0 0 0 0 0
w1=2, v1=12 1 0 0 12 12 12 12
w2=1, v2= 10 2 0 10 12 22 22 22
w3=3, v3= 20 3 0 10 12 22 30 32
w4=2, v4= 15 4 0 10 15 25 30 37

 The remaining is V[3, 3]

 Here V[3, 3] = V[2, 3] so item 3 is not included
 V[2, 3]  V[1, 3] so item 2 is included
Example: To find composition of optimal subset
Item Capacity
j

i 0 1 2 3 4 5

0 0 0 0 0 0 0
w1=2, v1=12 1 0 0 12 12 12 12
w2=1, v2= 10 2 0 10 12 22 22 22
w3=3, v3= 20 3 0 10 12 22 30 32
w4=2, v4= 15 4 0 10 15 25 30 37
 The remaining is V[1,2]
 V[1, 2]  V[0, 2] so item 1 is included

 The solution is {item 1, item 2, item 4}

 Total weight is 5
 Total value is 37
 The Knapsack Problem
 The time efficiency and space efficiency of this
algorithm are both in θ(nW).

 The time needed to find the composition of an

optimal solution is in O(n + W).
End of Chapter 8
ANALYSIS AND DESIGN OF
ALGORITHMS

UNIT-IV
CHAPTER 9:
GREEDY TECHNIQUE
 OUTLINE
 Greedy Technique
 Prim’s Algorithm
 Kruskal’s Algorithm
 Dijkstra’s Algorithm
 Minimum Spanning Tree
Definition: A spanning tree of a connected graph is its connected acyclic
subgraph (i.e., a tree) that contains all the vertices of the graph. A
minimum spanning tree of a weighted connected graph is its spanning
tree of 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.

Figure: Graph and its spanning trees: T1 is the minimum spanning tree.
 GREEDY APPROACH
 The greedy approach suggests constructing a solution through a
sequence of steps, each expanding a partially constructed
solution obtained so far, until a complete solution to the problem
is reached. On each step—and this is the central point of this
technique—the choice made must be

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

 locally optimal, i.e., it has to be the best local choice among all
feasible choices available on that step.

 irrevocable, i.e., once made, it cannot be changed on

subsequent steps of the algorithm.
 PRIM’S ALGORITHM
 Prim’s algorithm constructs a minimum spanning tree through a
sequence of expanding subtrees.

 The initial subtree in such a sequence consists of a single vertex

selected arbitrarily from the set V of the graph’s vertices.

 On each iteration, we expand the current tree in the greedy

manner by simply attaching to it the nearest vertex not in that
tree.

 The algorithm stops after all the graph’s vertices have been
included in the tree being constructed.

 Since the algorithm expands a tree by exactly one vertex on each

of its iterations, the total number of such iterations is n-1, where n
is the number of vertices in the graph.
PRIM’S ALGORITHM

6
 PRIM’S ALGORITHM
 The nature of Prim’s algorithm makes it necessary to provide
each vertex not in the current tree with the information about the
shortest edge connecting the vertex to a tree vertex.
 We can provide such information by attaching two labels to a
vertex: the name of the nearest tree vertex and the weight
(length) of the corresponding edge.
 Vertices that are not adjacent to any of the tree vertices can be
given the ∞ label and a null label for the name of the nearest tree
vertex.
 We can split the vertices that are not in the tree into two sets, the
“fringe” and the “unseen”.
 The fringe contains only the vertices that are not in the tree
but are adjacent to at least one tree vertex. These are the
candidates from which the next tree vertex is selected.
 The unseen vertices are all other vertices of the graph.
 Figure: Application of Prim’s Algorithm. The parenthesized labels of a vertex in the
middle column indicate the nearest tree vertex and edge weight; selected
vertices and edges are shown in bold.

b 1 c
3 4 4 6
a 5 5
f d
6 2 8
e
Tree vertices Remaining vertices Illustration

3 b 1 c
6
a(-, -) b(a, 3) c(-, ∞) d(-, ∞) e(a, 6) 4 4
f(a, 5) a f d
5 5
2
6 8
e
3
b 1
c
6
b(a, 3) c(b, 1) d(-, ∞) e(a, 6) f(b, 4) 4 4
a f 5 d
5
2
6 8
e
 Figure: Application of Prim’s Algorithm. The parenthesized labels of a vertex in the
middle column indicate the nearest tree vertex and edge weight; selected
vertices and edges are shown in bold.
Tree vertices Remaining vertices Illustration

3
b 1 c
c(b, 1) d(c, 6) e(a, 6) f(b, 4) 6
4 4
a 5 f 5 d
6 2 8
e
3 b 1
c
6
f(b, 4) d(f, 5) e(f, 2) 4 4
a f 5 d
5
2 8
6
e
3
b 1
c
6
e(f, 2) d(f, 5) 4 4
a f 5 d
5
2 8
6
d(f, 5) e
 PRIM‘S ALGORITHM PROBLEM

5
A B
4 6 2

2 D 3
C

3 1 2
E F
4
 PRIM’S ALGORITHM ANALYSIS

 Efficiency of Prim’s algorithm depends on the data

structures chosen for the graph.

 If a graph is represented by its weight matrix, the

algorithm’s running time will be in θ(|V |2).

 If a graph is represented by its adjacency linked lists, the

running time of the algorithm is in O(|E| log |V |).
 KRUSKAL’S ALGORITHM
 This is another greedy algorithm for the minimum spanning tree
problem that also always yields an optimal solution.

 It is named Kruskal’s algorithm, after Joseph Kruskal, who

discovered the algorithm.

 Kruskal’s algorithm looks at a minimum spanning tree for a

weighted connected graph G={V, E} as an acyclic subgraph with
|V| - 1 edges for which the sum of the edge weights is the
smallest.
 KRUSKAL’S ALGORITHM

 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.

 The algorithm begins by sorting the graph’s edges in

nondecreasing order of their weights.

 Then, starting with the empty subgraph, it scans this sorted list
adding the next edge on the list to the current subgraph if such an
inclusion does not create a cycle and simply skipping the edge
otherwise.
KRUSKAL’S ALGORITHM
 Figure: Application of Kruskal’s Algorithm. Selected edges are shown in bold.

b 1 c
3 4 4 6
a 5 5
f d
6 2 8
e
Tree vertices Sorted list of edges Illustration

3 b 1 c
6
bc ef ab bf cf af df ae cd de 4 4
1 2 3 4 4 5 5 6 6 8 a f d
5 5
2
6 8
e
b 1
c
3 6
bc bc ef ab bf cf af df ae cd de 4 4
1 1 2 3 4 4 5 5 6 6 8 a f 5 d
5
2
6 8
e
 Figure: Application of Kruskal’s Algorithm. Selected edges are shown in bold.

Tree vertices Sorted list of edges Illustration

3
b 1 c
6
ef bc ef ab bf cf af df ae cd de 4 4
2 1 2 3 4 4 5 5 6 6 8 a 5 f 5 d
2
6 8
e
3 b 1
c
ab bc ef ab bf cf af df ae cd de 6
3 1 2 3 4 4 5 5 6 6 8 4 4
a f 5 d
5
2 8
6
e
bf bc ef ab bf cf af df ae cd de 3
b 1
c
6
4 1 2 3 4 4 5 5 6 6 8 4 4
a f 5 d
5
df 2
6 8
5 e
 KRUSKAL‘S ALGORITHM
5
A B
4 6 2

2 D 3
C

3 1 2
E F
4

ANALYSIS
With an efficient sorting algorithm, efficiency of Kruskal’s
algorithm will be in O(|E| log |E |).
 DIJKSTRA’S ALGORITHM

 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.

 The best-known algorithm for the single-source

shortest-paths problem is Dijkstra’s algorithm.

 Edsger W. Dijkstra discovered this algorithm in mid-

1950s.
 DIJKSTRA’S ALGORITHM

 Assumptions:
 the graph is connected
 the edges are undirected (or directed)
 the edge weights are nonnegative
 DIJKSTRA’S ALGORITHM
 First, it finds the shortest path from the source to a vertex
nearest to it, then to a second nearest, and so on.

 Before its ith iteration commences, the algorithm has already

identified the shortest paths to i - 1 other vertices nearest to the
source.

 These vertices, the source, and the edges of the shortest paths
leading to them from the source form a subtree Ti of the given
graph.

 The set of vertices adjacent to the vertices in Ti can be referred to

as “fringe vertices”; they are the candidates from which
Dijkstra’s algorithm selects the next vertex nearest to the source.
 DIJKSTRA’S ALGORITHM
 To identify the ith nearest vertex, the algorithm computes, for
every fringe vertex u, the sum of the distance to the nearest tree
vertex v (given by the weight of the edge (v, u)) and the length dv
of the shortest path from the source to v.

 Then selects the vertex with the smallest such sum.

 Figure: Application of Dijkstra’s Algorithm. The next closest vertex is
shown in bold.
4
b c
3 6
2 5
a d e
7 4

Tree vertices Remaining vertices Illustration

4
3 b c
6
a(-, 0) b(a, 3) c(-, ∞) d(a, 7) e(-, ∞) 2 5
a d e
7 4

4
3
b c
b(a, 3) c(b, 3+4) d(b, 3+2) e(-, ∞) 6
2 5
a d e
7 4
 Figure: Application of Dijkstra’s Algorithm. The next closest vertex is
shown in bold.

Tree vertices Remaining vertices Illustration

4
d(b, 5) c(b, 7) e(d, 5+4) 3 b c
6
2 5
a d e
7 4
4
c(b, 7) e(d, 9) b c
3 6
2 5
e(d, 9) a d e
7 4
The shortest paths and their lengths are:
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
DIJKSTRA’S ALGORITHM

24
 DIJKSTRA’S ALGORITHM ANALYSIS
 The time efficiency of Dijkstra’s algorithm depends on
the data structures used for representing an input
graph.

 It is in θ(|V |2) for graphs represented by their weight

matrix.

 For graphs represented by their adjacency linked lists

it is in O(|E| log |V |).
End of Chapter 9