UNIT 4

Dynamic Programming, Backtracking and

Branch and Bound

Design & Analysis of Algorithms

Dr. Hirdesh Sharma
BCS 503
Assistant Professor
B.Tech 5th Sem CSE Deptt.

Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 1
11/19/2024
 Syllabus

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 2
 Course Objective

• Upon completion of this course, students will be able to do the

following:
• Analyze the asymptotic performance of algorithms.
• Write rigorous correctness proofs for algorithms.
• Demonstrate a familiarity with major algorithms and data structures.
• Apply important algorithmic design paradigms and methods of
analysis.
• Synthesize efficient algorithms in common engineering design
situations.

Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4
11/19/2024 3
 Unit Content

• Dynamic programming
• All pair shortest paths – Warshal’s and Floyd’s algorithms,
• . Knapsack
• Longest Common Sub Sequence
• Matrix Chain Multiplication
• Resource allocation problem(BFS, DFS)
• Backtracking
• Branch and Bound with examples such as Travelling Salesman
Problem
• Graph Coloring
• n-Queen Problem
• Hamiltonian Cycles
• Sum of subsets

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 4
 Unit Objective

• This. objective of this unit is to make students understand about

• Dynamic Programming
• Back tracking
• Branch and Bound ..

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 5
 Topic Objective

• This objective of this topic is to make students understand about

• Concepts of dynamic programming.
• Knapsack Problem(0/1)
• Floyd Warshall Algorithm
• Resource Allocation problem

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 6
 Dynamic Programming(CO4)

• Greedy Method and Dynamic Programming both are used for

solving optimization problem , both are different strategies but
purpose is same.
• In Greedy method we try to follow predefined procedures to
get optimal result.
• In dynamic we find all possible solution and then
• Pick up the best optimal solution .
• Dynamic Programming approach is different and bit time
consuming compared to greedy.
• Dynamic programming is formed using recursive formula.

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 7
 Dynamic Programming(CO4)

• In the divide-and-conquer strategy, you divide the problem to

be solved into subproblems.
• The subproblems are further divided into smaller subproblems.
• That task will continue until you get subproblems that can be
solved easily.
• The basic idea of dynamic programming is to use a table to
store the solutions of solved subproblems.
• If you face a subproblem again, you just need to take the
solution in the table without having to solve it again.
• Therefore, the algorithms designed by dynamic programming
are very effective.

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 8
 Dynamic Programming

To solve a problem by dynamic programming, you need to do the

following tasks:
 Find solutions of the smallest subproblems.
 Find out the formula (or rule) to build a solution of subproblem
through solutions of even smallest subproblems.
 Create a table that stores the solutions of subproblems. Then
calculate the solution of subproblem according to the found
formula and save to the table.
 From the solved subproblems, you find the solution of the
original problem.

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 9
 Dynamic Programming(CO4)

All Pair Shortest Path(Floyd-Warshall algorithm)

• The all pair shortest path algorithm is also known as Floyd-

Warshall algorithm is used to find all pair shortest path problem
from a given weighted graph.

• As a result of this algorithm, it will generate a matrix, which will

represent the minimum distance from any node to all other nodes in
the graph.

• At first the output matrix is same as given cost matrix of the graph.
After that the output matrix will be updated with all vertices k as the
intermediate vertex.

• The time complexity of this algorithm is O(V3), here V is the

number of vertices in the graph.

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 10
 Dynamic Programming(CO4)

All Pair Shortest Path(Floyd-Warshall algorithm)

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 11
 Dynamic Programming(CO4)

All Pair Shortest Path(Floyd-Warshall algorithm)

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 12
 Dynamic Programming(CO4)

All Pair Shortest Path(Floyd-Warshall algorithm)

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 13
 Dynamic Programming(CO4)

All Pair Shortest Path(Floyd-Warshall

algorithm)
Create a |V| x |V| matrix // It represents the distance
between every pair of vertices as given
1. For each cell (i,j) in M do-
2. if i = = j
3. M[ i ][ j ] = 0 // For all diagonal elements, value = 0
4. if (i , j) is an edge in E
5. M[ i ][ j ] = weight(i,j) // If there exists a direct edge
between the vertices, value = weight of edge

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 14
 Dynamic Programming(CO4)

else
6. M[ i ][ j ] = infinity // If there is no direct edge
between the vertices, value = ∞
7. for k from 1 to |V|
8. for i from 1 to |V|
9. for j from 1 to |V|
10. if M[ i ][ j ] > M[ i ][ k ] + M[ k ][ j ]
11. M[ i ][ j ] = M[ i ][ k ] + M[ k ][ j ]

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 15
 Dynamic Programming(CO4)

• Time Complexity-

• Floyd Warshall Algorithm consists of three

loops over all the nodes.
• The inner most loop consists of only constant
complexity operations.
• Hence, the asymptotic complexity of Floyd
Warshall algorithm is O(n3).
• Here, n is the number of nodes in the given
graph.
11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 16
 Practise Question

Q.1 Consider the following directed weighted graph-

Using Floyd Warshall Algorithm, find the shortest
path distance between every pair of vertices.

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 17
 Dynamic Programming(CO4)

Knapsack problem(0/1)
• As the name suggests, items are indivisible
here.
• We can not take the fraction of any item.
• We have to either take an item completely or
leave it completely.
• It is solved using dynamic programming
approach.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 18
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 19
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 20
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 21
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Knapsack problem(0/1)

• Consider a thief gets into a home to rob and he carries a knapsack.

There are fixed number of items in the home — each with its own
weight and value — Jewelry, with less weight and highest value vs
tables, with less value but a lot heavy.

• To add fuel to the fire, the thief has an old knapsack which has
limited capacity.

• Obviously, he can’t split the table into half or jewelry into 3/4ths. He
either takes it or leaves it.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 22
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Q.1 ) For the given set of items and knapsack capacity = 5 kg, find
the optimal solution for the 0/1 knapsack problem making use of
dynamic programming approach. ‘OR’
A thief enters a house for robbing it. He can carry a maximal weight
of 5 kg into his bag. There are 4 items in the house with the
following weights and values. What items should thief take if he
either takes the item completely or leaves it completely?

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 23
 Dynamic Programming(CO4)

• Knapsack capacity (w) = 5 kg

• Number of items (n) = 4
Draw a table say ‘T’ with (n+1) = 4 + 1 = 5
number of rows and (capacity+1) = 5 + 1 = 6
number of columns.

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 24
 Dynamic Programming(CO4)

Start filling the table row wise top to bottom from left to
right using the formula-
T (i , j) = max { T ( i-1 , j ) , valuei + T( i-1 , j – weighti )
}
inding T(1,1)-

We have,
i=1
j=1
(value)i = (value)1 = 3
(weight)i = (weight)1 = 2

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 25
 Dynamic Programming(CO4)

Substituting the values, we get-

T(1,1) = max { T(1-1 , 1) , 3 + T(1-1 , 1-2) }
T(1,1) = max { T(0,1) , 3 + T(0,-1) }
T(1,1) = T(0,1) { Ignore T(0,-1) }
T(1,1) = 0
Similarly compute for all enteries T(1,3) , T(1,4) ,T(1,5),
T(2,1) ,…..

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 26
 Dynamic Programming(CO4)

Dynamic-Programming Approach
• Let i be the highest-numbered item in an optimal
solution S for W dollars. Then S' = S - {i} is an optimal solution
for W - wi dollars and the value to the solution S is Vi plus the value
of the sub-problem.
• We can express this fact in the following formula: define c[i, w] to
be the solution for items 1,2, … , i and the maximum weight w.
• The algorithm takes the following inputs
• The maximum weight W
• The number of items n
• The two sequences v = <v1, v2, …, vn> and w = <w1, w2, …, wn>

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 27
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Dynamic-0-1-knapsack (v, w, n, W)

• for w = 0 to W do
• c[0, w] = 0 // c is matrix, its row 0
• for i = 1 to n do
• c[i, 0] = 0 // column is 0
• for w = 1 to W do
• if wi ≤ w then
• if vi + c[i-1, w-wi] then
• c[i, w] = vi + c[i-1, w-wi]
• else c[i, w] = c[i-1, w]
• else
• c[i, w] = c[i-1, w]

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 28
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

• Knapsack problem(0/1)

• The set of items to take can be deduced from the table, starting
at c[n, w] and tracing backwards where the optimal values came
from.
• If c[i, w] = c[i-1, w], then item i is not part of the solution, and we
continue tracing with c[i-1, w]. Otherwise, item i is part of the
solution, and we continue tracing with c[i-1, w-W].

Analysis

• This algorithm takes θ(n, w) times as table c has (n + 1).(w + 1)

entries, where each entry requires θ(1) time to compute.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 29
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Knapsack problem(0/1)

• If we want to include item 2, the maximum value we can obtain with

item 2 is the value of item 2 (40) + the maximum value we can
obtain with the remaining capacity (which is 0, because the
knapsack is completely full already).

• At row 3 (item 2), and column 10 (knapsack capacity of 9), again,

we can choose to either include item 2 or not.

• If we choose not to, the maximum value we can obtain is the same
as that in the row above at the same column, i.e. 10 (by including
only item 1, which has a value of 10).

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 30
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

• Knapsack problem(0/1)

• If we include item 2, we have a remaining knapsack capacity of 9 -

4 = 5.

• We can find out the maximum value that can be obtained with a
capacity of 5 by looking at the row above, at column 5.

• Thus, the maximum value we can obtain by including item 2 is 40

(the value of item 2) + 10 = 50.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 31
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Knapsack problem(0/1)

• We pick the larger of 50 vs 10, and so the maximum value we can

obtain with items 1 and 2, with a knapsack capacity of 9, is 50.

• Once the table has been populated, the final solution can be found at
the last row in the last column, which represents the maximum value
obtainable with all the items and the full capacity of the knapsack.

• For more examples watch the following youtube link

• https://www.youtube.com/watch?v=oTTzNMHM05I

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 32
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

• The longest common subsequence (LCS) is defined as the

longest subsequence that is common to all the given sequences,
provided that the elements of the subsequence are not required
to occupy consecutive positions within the original sequences.
• If S1 and S2 are the two given sequences then, Z is the common
subsequence of S1 and S2 if Z is a subsequence of
both S1 and S2. Furthermore, Z must be a strictly increasing
sequence of the indices of both S1 and S2.
• In a strictly increasing sequence, the indices of the elements
chosen from the original sequences must be in ascending order
in Z.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 33
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

• If S1={B,C,D,A,A,C,D} then, {A,D,B} cannot

be a subsequence of S1 as the order of the
elements is not the same (ie. not strictly
increasing sequence).
• Let us understand LCS with an example:
If S1 = {B,C,D,A,A,C,D}
S2 = {A,C, D,B,A,C}
Then, common subsequences are:
{B,C}{C,D,A,C}{D,A,C}{A,A,C}{A,C}{C,D}…

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 34
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

Among these subsequences, {C,D,A,C} is the

longest common subsequence. We are going to
find this longest common subsequence using
dynamic programming.
Application :
natural language processing, and text
comparison.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 35
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

Using Dynamic Programming to find the LCS

• Let us take two sequences:

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 36
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

The following steps are followed for finding the

longest common subsequence. :-
1. Create a table of dimension n+1*m+1 where n
and m are the lengths of X and Y respectively.
The first row and the first column are filled
with zeros.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 37
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

2. Fill each cell of the table using the following logic.

3. If the character corresponding to the current row and current

column are matching, then fill the current cell by adding one to
the diagonal element. Point an arrow to the diagonal cell.

4. Else take the maximum value from the previous column and
previous row element for filling the current cell. Point an arrow
to the cell with maximum value. If they are equal, point to any
of them.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 38
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 39
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

5. Step 2 is repeated until the table is filled.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 40
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

6. The value in the last row and the last

column is the length of the longest common
subsequence.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 41
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

• In order to find the longest common

subsequence, start from the last element and
follow the direction of the arrow. The elements
corresponding to () symbol form the longest
common subsequence.

• Thus, the longest common subsequence is C,A

Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 42
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

Q. )How is a dynamic programming algorithm

more efficient than the recursive algorithm while
solving an LCS problem?

• The method of dynamic programming reduces the

number of function calls. It stores the result of
each function call so that it can be used in future
calls without the need for redundant calls.

• In the above dynamic algorithm, the results

obtained from each comparison between elements
of X and the elements of Y are stored in a table so
that they can be used in future computations.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 43
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)

• So, the time taken by a dynamic approach is

the time taken to fill the table (ie. O(mn)).
Whereas, for recursion algorithm there are 2^m
possible subsequences of X and 2^n possible
subsequences of Y. So in this recursive
approach, we are comparing each subsequence
of X with each subsequence of Y. So the overall
time complexity is O(2^m * 2^n) = O(2^(m +
n)), which is inefficient for large values of m
and ie; 2max(m,n)
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 44
and Analysis of Algorithm Unit 4
 Longest Common Sub Sequence(CO4)
Longest Common Subsequence Algorithm
X and Y be two given sequences
Initialize a table LCS of dimension X.length * Y.length
X.label = X //Row is representing X string
Y.label = Y //column is representing Y string
LCS[0][] = 0
LCS[][0] = 0
Start from LCS[1][1]
Compare X[i] and Y[j]
If X[i] == Y[j]
LCS[i][j] = 1 + LCS[i-1, j-1]
Point an arrow to LCS[i][j]
Else
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
Point an arrow to max(LCS[i-1][j], LCS[i][j-1])
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 45
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Resource Allocation problem

• An optimal allocation of resources is defined by a maximum cost of

a path from S to T.

• A dynamic programming formulation for a k-stage is obtained by

first noticing that every S to T path is result of a sequence k-2
decisions.
• Let c(S,k) be a cost of path from node S to k and d( k, T) be the cost
of path from node k to T, via. some intermediate node , which can be
calculated recursively.

d(S,T)= max{c(S,k) +d(k,T)}

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 46
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Resource Allocation problem

• A resource allocation problem in which ‘m’ resources are to be

allocated to ‘n’ projects. If ‘j’ resources are allocated to project I
then profit is P(i,j).

• The problem is to allocate the resource to the ‘n’ projects in such a

way as to maximize total next profit.

• This problem can be formulated as an n+1 stage graph problem as

follows . Stage i, 0≤i≤ n-1, represents project I, there are m+1
vertices, associated with stage i, 1≤i≤ n-1, stage 0 and n each one
vertex S and T respectively. Vertex (i,j) represents I, resources
allocated to projects 1,2,……..j.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 47
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

Resource Allocation problem

• An optimal allocation of resources is defined by a maximum cost of

a path from S to T.

• A dynamic programming formulation for a k-stage is obtained by

first noticing that every S to T path is result of a sequence k-2
decisions.
• Let c(S,k) be a cost of path from node S to k and d( k, T) be the cost
of path from node k to T, via. some intermediate node , which can be
calculated recursively.

d(S,T)= max{c(S,k) +d(k,T)}

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 48
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

• Consider the following example to understand the concept of

multistage graph.

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/d
esign_and_analysis_of_algorithms_multistage_graph.htm

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 49
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

• According to the formula, we have to calculate the cost (i, j) using

the following steps

• Step-1: Cost (K-2, j)

• In this step, three nodes (node 4, 5. 6) are selected as j. Hence, we

have three options to choose the minimum cost at this step.

Cost(3, 4) = min {c(4, 7) + Cost(7, 9),c(4, 8) + Cost(8, 9)} = 7

Cost(3, 5) = min {c(5, 7) + Cost(7, 9),c(5, 8) + Cost(8, 9)} = 5
Cost(3, 6) = min {c(6, 7) + Cost(7, 9),c(6, 8) + Cost(8, 9)} = 5

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 50
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

• Step-2: Cost (K-3, j)

• Two nodes are selected as j because at stage k - 3 = 2 there are two
nodes, 2 and 3. So, the value i = 2 and j = 2 and 3.

Cost(2, 2) = min {c(2, 4) + Cost(4, 8) + Cost(8, 9),c(2, 6) +

Cost(6, 8) + Cost(8, 9)}
=8
Cost(2, 3) = {c(3, 4) + Cost(4, 8) + Cost(8, 9), c(3, 5) + Cost(5, 8)+
Cost(8, 9), c(3, 6) + Cost(6, 8) + Cost(8, 9)}
= 10

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 51
and Analysis of Algorithm Unit 4
 Dynamic Programming(CO4)

• Step-3: Cost (K-4, j)

Cost (1, 1) = {c(1, 2) + Cost(2, 6) + Cost(6, 8) + Cost(8, 9), c(1, 3)
+
Cost(3, 5) + Cost(5, 8) + Cost(8, 9))}
= 12
c(1, 3) + Cost(3, 6) + Cost(6, 8 + Cost(8, 9))} = 13
Hence, the path having the minimum cost is 1→ 3→ 5→ 8→ 9.

For more examples refer the video

https://www.youtube.com/watch?v=9iE9Mj4m8jk

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 52
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

• Matrix Chain Multiplication is an algorithm

that is applied to determine the lowest cost way
for multiplying matrices.
• The actual multiplication is done using the
standard way of multiplying the matrices, i.e., it
follows the basic rule that the number of rows
in one matrix must be equal to the number of
columns in another matrix.
• Hence, multiple scalar multiplications must be
done to achieve the product.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 53
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

******FEW POINTS TO MEMORIZE *****

first , condition to multiply two matrices is column of first should be
equal to num of rows of second matrice

second point is : resultant matrix dimension will be equal to num of row

of first matrix and num of column of second matrix.

third point is for generating third matrix num of multication required is

eg: M1 = 2 X 3 , M2= 3 X 2 so for M3 multiplications will be 2 X 3 X 2
= 12

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 54
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

From this it is seen that A1 (A2 .A3) is better .

For Larger num of matrices there may be different possibilities and one of the possibility is
best possible way . So, we have to find the best possible paranthesises such that total cost of
multiplication is minimized.
Suppose there are 10 matrices , for which we have to find best possible parenthesis doing this
way is not possible so we need some
11/19/2024
formula.
Dr. Hirdesh Sharma BCS 503 Design
55
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

• consider matrices A, B, C, and D, to be multiplied;

hence, the multiplication is done using the standard
matrix multiplication.
• There are multiple combinations of the matrices found
while using the standard approach since matrix
multiplication is associative. For instance, there are five
ways to multiply the four matrices given above −
1. A ( B (CD) )
2. A ((BC) D )
3. (A B) (C D)
4. ( A ( BC ) ) D
5. ( ( AB ) C ) D
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 56
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

• The number of ways in which the input matrices

can be multiplied using the formulae −
2n ^ C n / (n+1)
Here we take n as (number of matrices -1)
So ,

for n=4 matrices

= 2*3 ^C 3 / 4
= 6^C 3 /4 = (6 *5*4) / (3*2*1) divided by 4
so, we get 5 possibilities.
Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm
11/19/2024 57
Unit 4
 Matrix Chain Multiplication

So, dynamic programming approach of the

matrix chain multiplication is adopted in order
to find the combination with the lowest cost.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 58
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

Applying the dynamic programming approach

formula find the costs of various
parenthesizations

C[1,1]=0
C[2,2]=0
C[3,3]=0
C[4,4]=0
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 59
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

d0 , d1 … are dimensions of matrix , if we find like this it goes on expanding as

we can see we need c[2,4] value and c[3,4]… so for
Dr. Hirdesh Sharma BCS 503
this we understand that we
Design
11/19/2024 60
will start finding from small values.
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

For this we will prepare a table.The table is

known as a cost table, where all the cost values
calculated from the different combinations of
parenthesis are stored.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 61
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

First find values with 1 difference then 2 difference

and so on…here we are preparing 2 tables one for
cost and another for value of K for which we are
getting minimum cost in table.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 62
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

If we start with difference of 0 so we get :

C[1,1]=0
C[2,2]=0
C[3,3]=0
C[4,4]=0
Now for difference of 1 we are finding

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 63
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 64
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 65
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

On continuing this we get

Here number of scalar multiplication is 58

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 66
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

Now that all the values in cost table are computed, the
final step is to parethesize the sequence of matrices.
For that, k table needs to be constructed with the
minimum value of ‘k’ corresponding to every
parenthesis.

Based on the lowest cost values from the cost table and
their corresponding k values, let us add parenthesis on
the sequence of matrices.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 67
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

Matrix Chain Multiplication Algorithm

• Matrix chain multiplication algorithm is only
applied to find the minimum cost way to multiply a
sequence of matrices. Therefore, the input taken by
the algorithm is the sequence of matrices while the
output achieved is the lowest cost parenthesization.
1. Count the number of parenthesizations. Find the
number of ways in which the input matrices can
be multiplied.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 68
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

2. Once the parenthesization is done, the optimal

substructure must be devised as the first step of
dynamic programming approach so the final product
achieved is optimal. In matrix chain multiplication, the
optimal substructure is found by dividing the sequence
of matrices A[i….j] into two parts A[i,k] and A[k+1,j].
It must be ensured that the parts are divided in such a
way that optimal solution is achieved. Find the lowest
cost parenthesization of the sequence of matrices by
constructing cost tables and corresponding k values
table.
3. Once the lowest cost is found, print the
corresponding parenthesization as the output.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 69
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

Pseudocode
MATRIX-CHAIN-MULTIPLICATION(p)
n = p.length ─ 1
let m[1…n, 1…n] and s[1…n ─ 1, 2…n] be new matrices //s is
described for matrix K
for i = 1 to n
m[i, i] = 0
for l = 2 to n // l is the chain length
for i = 1 to n - l + 1
j=i+l-1
m[i, j] = ∞
for k = i to j - 1
q = m[i, k] + m[k + 1, j] + pi-1pkpj
if q < m[i, j]
m[i, j] = q
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 70
and Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

Pseudocode to print the optimal output

parenthesization −
PRINT-OPTIMAL-OUTPUT(s, i, j )
if i == j
print “A”I
else
print “(” PRINT-OPTIMAL-OUTPUT(s, i, s[i, j])
PRINT-OPTIMAL-OUTPUT(s, s[i, j] + 1, j) print “)”

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 71
and Analysis of Algorithm Unit 4
 Backtracking(CO4)- Objective

This objective of this topic is to make students understand

about
• Concepts of Backtracking
• Graph Colouring
• N-Queens
• Sum of Subsets
• Hamiltonian Cycle

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 72
and Analysis of Algorithm Unit 4
 Prerequisite and Recap

• Prerequisite
• Algorithms Concepts
• C programming
• Graph

• Recap
• Dynamic Programming

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 73
and Analysis of Algorithm Unit 4
 Backtracking (CO4)

• Backtracking is an algorithmic-technique for solving problems

recursively by trying to build a solution incrementally, one piece
at a time, removing those solutions that fail to satisfy the
constraints of the problem at any point of time.

• Backtracking uses brute force approach. Brute Force approach

says that for any given problem generate all possible solution and
pick up the desired solution. (*we do same in DP but we r finding
optimal solution in it , Backtracking is used wen we have multiple
solution and we want all the solution*).

• It removes the solutions that doesn't give rise to the solution of the
problem based on the constraints given to solve the problem.

• Backtracking uses Depth First Search to generate state space tree.

Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 74
and Analysis of Algorithm Unit 4
 Backtracking (CO4)

Example :

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 75
and Analysis of Algorithm Unit 4
 Backtracking (CO4)

Problems that we solve using backtracking are those problems which

usually have some constraints and we are trying to find those
constraints and get the solution which are satisfying those
constraints.
Eg :- suppose one constraint is G1 should not sit in between, then
find possible solution.

**if no bounding func.

Is applied until you
Reach at last level then
You got a solution.

Here we got 4 solution

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 76
and Analysis of Algorithm Unit 4
 Backtracking

• Backtracking algorithm is applied to some specific types of

problems.
• Decision problem used to find a feasible solution of the
problem.
• Optimisation problem used to find the best solution that can
be applied.
• Enumeration problem used to find the set of all feasible
solutions of the problem

• In backtracking problem, the algorithm tries to find a sequence

path to the solution which has some small checkpoints from
where the problem can backtrack if no feasible solution is found
for the problem.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 77
and Analysis of Algorithm Unit 4
 Backtracking

For Example,

• Here, Green is the start point, blue is the intermediate point, red are
points with no feasible solution, dark green is end solution.

• when the algorithm propagates to an end to check if it is a solution

or not, if it is then returns the solution otherwise backtracks to the
point one step behind it to find track to the next point to find
solution.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 78
and Analysis of Algorithm Unit 4
 Backtracking

ALGORITHM

Step 1 − if current_position is goal, return success

Step 2 − else,

Step 3− if current_position is an end point, return failed.

Step 4− else, if current_position is not end point, explore

and repeat above steps.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 79
and Analysis of Algorithm Unit 4
 Backtracking(GRAPH COLORING)

Graph coloring can be described as a process to color

graph components such as vertex , edges and region
under some constraints.

In this, the same color should not be used to fill the two
adjacent vertices.

Example of Graph coloring

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 80
and Analysis of Algorithm Unit 4
 Backtracking(GRAPH COLORING)

Applications of Graph coloring

there are various applications of graph coloring.

Assignment
Map coloring
Radiofrequency
Scheduling the tasks
Sudoku
Prepare time table

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 81
and Analysis of Algorithm Unit 4
 Backtracking(GRAPH COLORING)

Chromatic Number
The chromatic number can be described as the
minimum number of colors required to properly
color any graph.

In Above graph ,Few points are :-

The same color is not used to color the two
adjacent vertices.
11/19/2024
Dr. Hirdesh Sharma BCS 503
and Analysis of Algorithm
Design
Unit 4
82
 Backtracking(GRAPH COLORING)

•The minimum number of colors of this graph is

3, which is needed to properly color the vertices.

•Hence, in this graph, the chromatic number = 3

•If we want to properly color this graph, in this

case, we are required at least 3 colors.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 83
and Analysis of Algorithm Unit 4
 Backtracking(GRAPH COLORING)

Graph Colouring Problem (M Coloring Problem)

• Given an undirected graph and a number m,
determine if the graph can be coloured with at most
m colours such that no two adjacent vertices of the
graph are colored with the same color.

• Here coloring of a graph means the assignment of

colors to all vertices.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 84
and Analysis of Algorithm Unit 4
 Backtracking(GRAPH COLORING)

Here Graph can be colored in different ways , that means there can be more than one
solutions possible.

Q.) A Graph is given and m=3(colors) is given , have to color graph such that no two
adjacent vertices a have same color .
(*So this problem can be solved using backtracking and in backtracking we generate a
state space tree*).

Sol) First generating state space tree without any condition.

1 2

4 3

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 85
and Analysis of Algorithm Unit 4
 Backtracking(GRAPH COLORING)

This tree is showing all possibility of coloring without showing adjacency condition(Means
neighbouring vertices can have same color also).
**So this graph becomes big if we do not apply any conditions.
*** total nodes without conditions = 1 +3 +3x3 +3x3X3 +…… = 3^4 (for 4 vertices)

But in backtracking we impose a condition and solve a problem

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 86
and Analysis of Algorithm Unit 4
 Backtracking(GRAPH COLORING)

Time Complexity: O(M^V). Reason: Choosing out of

M given colors for V vertices will lead to an O(M^V)
combination. So the time complexity is O(M^V).

Space Complexity: O(V).

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 87
and Analysis of Algorithm Unit 4
 N- Queens Problem

N- Queens Problem

• N - Queens problem is to place n - queens in such a manner on an

n x n chessboard that no queens attack each other by being in the
same row, column or diagonal.

• It can be seen that for n =1, the problem has a trivial solution, and
no solution exists for n =2 and n =3.

• So first we will consider the 4 queens problem and then generate

it to n - queens problem.

• Given a 4 x 4 chessboard and number the rows and column of the

chessboard 1 through 4.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 88
and Analysis of Algorithm Unit 4
 N- Queens Problem

N- Queens Problem

Since, we have to place 4 queens such as q1 q2 q3 and q4 on the

chessboard, such that no two queens attack each other. In such a
conditional each queen must be placed on a different row, i.e.,
we put queen "i" on row "i."

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 89
and Analysis of Algorithm Unit 4
 N- Queens Problem

N- Queens Problem

• Now, we place queen q1 in the very first acceptable position (1, 1).

• Next, we put queen q2 so that both these queens do not attack each
other.

• We find that if we place q2 in column 1 and 2, then the dead end is

encountered.

• Thus the first acceptable position for q2 in column 3, i.e. (2, 3) but
then no position is left for placing queen 'q3' safely.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 90
and Analysis of Algorithm Unit 4
 N- Queens Problem

N- Queens Problem

• So we backtrack one step and place the queen 'q2' in (2, 4), the
next best possible solution. Then we obtain the position for
placing 'q3' which is (3, 2).

• But later this position also leads to a dead end, and no place is
found where 'q4' can be placed safely.

• Then we have to backtrack till 'q1' and place it to (1, 2) and then
all other queens are placed safely by moving q2 to (2, 4), q3 to (3,
1) and q4 to (4, 3).

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 91
and Analysis of Algorithm Unit 4
 N- Queens Problem

Fig shows the complete state space for 4 - queens problem. But we can use
backtracking method to generate the necessary node and stop if the next node violates
the rule, i.e., if two queens are attacking.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 92
and Analysis of Algorithm Unit 4
 N- Queens Problem

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 93
and Analysis of Algorithm Unit 4
 N- Queens Problem

N- Queens Problem

• That is, we get the solution (2, 4, 1, 3).

• This is one possible solution for the 4-queens problem.

• For another possible solution, the whole method is repeated for

all partial solutions. The other solutions for 4 - queens problems
is (3, 1, 4, 2) i.e.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 94
and Analysis of Algorithm Unit 4
 N- Queens Problem

N- Queens Problem

• Fig shows the complete state space for 4 - queens problem. But
we can use backtracking method to generate the necessary node
and stop if the next node violates the rule, i.e., if two queens are
attacking.

• It can be seen that all the solutions to the 4 queens problem can
be represented as 4 - tuples (x1, x2, x3, x4) where xi represents
the column on which queen "qi" is placed.

Time complexity will be N * (N-1) * (N-2) …. i.e. N! O(N!), where 'N' is

the number of queens as we are using a 2-D array having N rows and N
columns.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 95
and Analysis of Algorithm Unit 4
 Backtracking

4- Queens Problem
(** while using backtracking we try to kill the node if it
does not satisfy bounding function **)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 96
and Analysis of Algorithm Unit 4
N- Queens Problem

8- Queens Problem

1.Thus, the solution for 8 -

queen problem for (4, 6, 8, 2, 7, 1, 3, 5).
2.If two queens are placed at position (i, j) and (k, l).
3.Then they are on same diagonal only if (i - j) = k -
l or i + j = k + l.
4.The first equation implies that j - l = i - k.
5.The second equation implies that j - l = k - i.
6.Therefore, two queens lie on the duplicate diagonal if an
d only if |j-l|=|i-k|
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 97
and Analysis of Algorithm Unit 4
 Hamiltonian Cycles

Hamiltonian Cycles
• Hamiltonian Path in an undirected graph is a path that visits each
vertex exactly once.
• A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian
Path such that there is an edge (in the graph) from the last vertex
to the first vertex of the Hamiltonian Path.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 98
and Analysis of Algorithm Unit 4
 Sum of Subsets Problem

• Subset sum problem is to find subset of elements that are

selected from a given set whose sum adds up to a given
number K.

• We are considering the set contains non-negative values. It is

assumed that the input set is unique (no duplicates are
presented).

• Here backtracking approach is used for trying to select a valid

subset when an item is not valid, we will backtrack to get the
previous subset and add another element to get the solution.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 99
and Analysis of Algorithm Unit 4
 Sum of Subsets Problem

Sum of Subsets Problem

• Subset sum problem is to find subset of elements that are
selected from a given set whose sum adds up to a given
number K.

• We are considering the set contains non-negative values. It is

assumed that the input set is unique (no duplicates are
presented).

• Here backtracking approach is used for trying to select a valid

subset when an item is not valid, we will backtrack to get the
previous subset and add another element to get the solution.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 100
and Analysis of Algorithm Unit 4
 Sum of Subsets Problem

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 101
and Analysis of Algorithm Unit 4
 Sum of Subsets Problem

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 102
and Analysis of Algorithm Unit 4
 Sum of Subsets Problem

Sum of Subsets Problem

Backtracking
. Algorithm for Subset Sum
Using exhaustive search we consider all subsets irrespective of
whether they satisfy given constraints or not. Backtracking can be
used to make a systematic consideration of the elements to be selected.

Algorithm
subsetSum(set, subset, n, subSize, total, node, sum)
Input: The given set and subset, size of set and subset, a total of the
subset, number of elements in the subset and the given sum.
Output: All possible subsets whose sum is the same as the given sum.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 103
and Analysis of Algorithm Unit 4
 Sum of Subsets Problem

Sum of Subsets Algorithm

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 104
and Analysis of Algorithm Unit 4
 Sum of Subsets Problem

Sum of Subsets Example

Given a set S = (3, 4, 5, 6) and X =9. Obtain the subset sum using
Backtracking approach.
Solution:
Initially S = (3, 4, 5, 6) and X =9.
S'= (∅)

• The implicit binary tree for the subset sum problem is shown in Fig.

• The number inside a node is the sum of the partial solution elements
at a particular level.

• Thus, if our partial solution elements sum is equal to the positive

integer 'X' then at that time search will terminate, or it continues if all
the possible solution needs to be obtained.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 105
and Analysis of Algorithm Unit 4
 Backtracking

Sum of Subsets Example

Input: The Set: {10, 7, 5, 18, 12, 20, 15}

The sum Value: 35
Output:
All possible subsets of the given set, where sum of each
element for every subsets is same as the given sum value.
{10, 7, 18}
{10, 5, 20}
{5, 18, 12}
{20, 15}

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 106
and Analysis of Algorithm Unit 4
 Branch and Bound(CO4)- Objective

This objective of this topic is to make students understand

about
• Concepts of Branch and Bound
• Travelling Salesman Problem

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 107
and Analysis of Algorithm Unit 4
 Prerequisite and Recap

• Prerequisite
• Algorithms Concepts
• C programming
• Graph

• Recap
• Backtracking

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 108
and Analysis of Algorithm Unit 4
 Branch and Bound (CO4)

• Branch and bound is an algorithm design paradigm which is

generally used for solving combinatorial optimization problems.

• These problems are typically exponential in terms of time

complexity and may require exploring all possible permutations in
worst case.

• The Branch and Bound Algorithm technique solves these problems

relatively quickly.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 109
and Analysis of Algorithm Unit 4
 Branch and Bound

Travelling Salesman Problem

Given a set of cities and distance between every pair of cities, the
problem is to find the shortest possible tour that visits every city
exactly once and returns to the starting point.

• In Branch and Bound method, for current node in tree, we

compute a bound on best possible solution that we can get if
we down this node.

• If the bound on best possible solution itself is worse than

current best (best computed so far), then we ignore the subtree
rooted with the node.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 110
and Analysis of Algorithm Unit 4
 Branch and Bound

Travelling Salesman Problem

Note that the cost through a node includes two costs.

1) Cost of reaching the node from the root (When we reach a node, we
have this cost computed)

2) Cost of reaching an answer from current node to a leaf (We compute

a bound on this cost to decide whether to ignore subtree with this node
or not).

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 111
and Analysis of Algorithm Unit 4
 Branch and Bound

Travelling Salesman Problem- Example

• In this method we expand the node which is most promising means the
node which promises that expanding or choosing it will give us the
optimal solution.

• So we prepare the tree starting from root then we expand it.

• The cost matrix is defined by

C(i,j) = W(i,j) , if there is a direct path from Ci to Cj.
=∞, If there is no direct path from Ci to Cj.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 112
and Analysis of Algorithm Unit 4
 Branch and Bound

Travelling Salesman Problem- Example

The initial cost matrix is :

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 113
and Analysis of Algorithm Unit 4
 Branch and Bound

Example continue……
• Now we will reduce the matrix To reduce a matrix,
perform the row reduction and column reduction of
the matrix separately.

• A row or a column is said to be reduced if it contains

at least one entry ‘0’ in it.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 114
and Analysis of Algorithm Unit 4
 Branch and Bound

Example continue…… •Select the least value element

• row reduction from that row.
•Subtract that element from
each element of that row.

•Reduce the elements of row-1 by 4.

•Reduce the elements of row-2 by 5.
•Reduce the elements of row-3 by 6.
•Reduce the elements of row-4 by 2.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 115
and Analysis of Algorithm Unit 4
 Branch and Bound

•Select the least value element

column reduction :
from that column.
• There is no need to reduce •Subtract that element from
column-1. each element of that column.
• There is no need to reduce
column-2.
• Reduce the elements of
column-3 by 1.
• There is no need to reduce
column-4.
Finally, the initial distance matrix is
completely reduced.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 116
and Analysis of Algorithm Unit 4
 Branch and Bound

Now, we calculate the cost of node-1 by adding all the

reduction elements.

Cost(1)
= Sum of all reduction elements
=4+5+6+2+1
= 18

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 117
and Analysis of Algorithm Unit 4
 Branch and Bound

Choosing To Go To Vertex-B: Node-2 (Path A → B)

1
From the reduced matrix, M[A,B] = 0 A

Set row-A and column-B to ∞

4
Set M[B,A] = ∞ 2
3
Now, resulting cost matrix is- B D
C

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 118
and Analysis of Algorithm Unit 4
 Branch and Bound

Now,
We reduce this matrix.
Then, we find out the cost of node-02.

Row Reduction-

We can not reduce row 1 as all its elements are ∞.

Reduce all the elements of row 2 by 13.
There is no need to reduce row 3.
There is no need to reduce row 4.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 119
and Analysis of Algorithm Unit 4
 Branch and Bound

we obtain the following row-reduced matrix-

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 120
and Analysis of Algorithm Unit 4
 Branch and Bound

Column Reduction- • we obtain the

following
• Reduce the elements of column 1 column-
reduced
by 5. matrix-
• We can not reduce column 2 as all
its elements are ∞.
• There is no need to reduce column-
3.
• There is no need to reduce column-
4.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 121
and Analysis of Algorithm Unit 4
 Branch and Bound

Finally, the matrix is completely reduced.

Now, we calculate the cost of node-2.
Cost(2)
= Cost(1) + Sum of reduction elements + M[A,B]
= 18 + (13 + 5) + 0
= 36
Choosing To Go To Vertex-C: Node-3 (Path A → C)

• From the reduced matrix of step-01, M[A,C] = 7

• Set row-A and column-C to ∞
• 11/19/2024
Set M[C,A] = ∞ Dr.andHirdesh Sharma BCS 503
Analysis of Algorithm
Design
Unit 4
122
 Branch and Bound

Row Reduction-
We can not reduce row-1 as all its elements are ∞.
There is no need to reduce row-2.
There is no need to reduce row-3.
There is no need to reduce row-4.
Thus, the matrix is already row-reduced.
Column Reduction-
There is no need to reduce column-1.
There is no need to reduce column-2.
We can not reduce column-3 as all its elements are ∞.
There is no need to reduce column-4.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 123
and Analysis of Algorithm Unit 4
 Branch and Bound

Thus, the matrix is already column reduced.

Finally, the matrix is completely reduced.
Now, we calculate the cost of node-3.

Cost(3)
= Cost(1) + Sum of reduction
elements + M[A,C]
= 11/19/2024
18 + 0 + 7 = 25 Dr.andHirdesh Sharma BCS 503
Analysis of Algorithm
Design
Unit 4
124
 Branch and Bound

Choosing To Go To Vertex-D: Node-4 (Path A → D)

From the reduced matrix of step-01, M[A,D] = 3

Set row-A and column-D to ∞
Set M[D,A] = ∞
resulting cost matrix is-

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 125
and Analysis of Algorithm Unit 4
 Branch and Bound

we find out the cost of node-04.

Row Reduction-
We can not reduce row-1 as all its elements are ∞.
There is no need to reduce row-2.
Reduce all the elements of row-3 by 5.
There is no need to reduce row-4.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 126
and Analysis of Algorithm Unit 4
 Branch and Bound

Column Reduction-
There is no need to reduce column-1.
There is no need to reduce column-2.
There is no need to reduce column-3.
We can not reduce column-4 as all its elements are ∞.
Now, we calculate the cost of node-4.
Cost(4)
= Cost(1) + Sum of reduction elements + M[A,D]
= 18 + 5 + 3
= 26
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 127
and Analysis of Algorithm Unit 4
 Branch and Bound

• Thus, we have-
• Cost(2) = 36 (for Path A → B)
• Cost(3) = 25 (for Path A → C)
• Cost(4) = 26 (for Path A → D)

We choose the node with the lowest cost.

Since cost for node-3 is lowest, so we prefer to visit node-
3.
Thus, we choose node-3 i.e. path A → C.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 128
and Analysis of Algorithm Unit 4
 Branch and Bound

Step-03:
We explore the vertices B and
D from node-3.
We now start from the cost
matrix at node-3 which is-

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 129
and Analysis of Algorithm Unit 4
 Branch and Bound

Choosing To Go To Vertex-B: Node-5 (Path A →

C → B)
From the reduced matrix of step-02, M[C,B] = ∞
Set row-C and column-B to ∞
Set M[B,A] = ∞

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 130
and Analysis of Algorithm Unit 4
 Branch and Bound

Find out cost of Node- 5

Row Reduction-

• We can not reduce row-1 as

all its elements are ∞.
• Reduce all the elements of
row-2 by 13.
• We can not reduce row-3 as
all its elements are ∞.
• Reduce all the elements of
row-4 by 8.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 131
and Analysis of Algorithm Unit 4
 Branch and Bound

Column Reduction-
• There is no need to reduce
column-1.
• We can not reduce column-2
as all its elements are ∞.
• We can not reduce column-3
as all its elements are ∞.
• There is no need to reduce
column-4.
Thus, the matrix is already
column reduced.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 132
and Analysis of Algorithm Unit 4
 Branch and Bound

Finally, the matrix is completely reduced.

Now, we calculate the cost of node-5.

Cost(5)
= cost(3) + Sum of reduction elements + M[C,B]
= 25 + (13 + 8) + ∞
=∞

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 133
and Analysis of Algorithm Unit 4
 Branch and Bound

Choosing To Go To Vertex-D: Node-6 (Path A → C →

D)
From the reduced matrix of step-02, M[C,D] = ∞
Set row-C and column-D to ∞
Set M[D,A] = ∞

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 134
and Analysis of Algorithm Unit 4
 Branch and Bound

Then, we find out the cost of node-6.

Row Reduction-

• We can not reduce row-1 as all its elements are ∞.

• There is no need to reduce row-2.
• We can not reduce row-3 as all its elements are ∞.
• We can not reduce column-4 as all its elements are ∞.
Thus, the matrix is already column reduced

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 135
and Analysis of Algorithm Unit 4
 Branch and Bound

Finally, the matrix is completely reduced.

Now, we calculate the cost of node-6.

Cost(6)
= cost(3) + Sum of reduction elements + M[C,D]
= 25 + 0 + 0
= 25
Thus, we have-
Cost(5) = ∞ (for Path A → C → B)
Cost(6) = 25 (for Path A → C → D)
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 136
and Analysis of Algorithm Unit 4
 Branch and Bound

Since cost for node-6 is lowest, so we prefer to visit

node-6.
Thus, we choose node-6 i.e. path C → D.
Step-04:
We explore vertex B from node-6.
We start with the cost matrix at node-6 which is-

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 137
and Analysis of Algorithm Unit 4
 Branch and Bound

Choosing To Go To Vertex-B: Node-7 (Path A → C →

D → B)
From the reduced matrix of step-03, M[D,B] = 0
Set row-D and column-B to ∞
Set M[B,A] = ∞
Now, resulting cost matrix is-

Now,
We reduce this matrix.
Then, we find out the cost of node-7.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 138
and Analysis of Algorithm Unit 4
 Branch and Bound

Row Reduction-
We can not reduce row-1 as all its elements are ∞.
We can not reduce row-2 as all its elements are ∞.
We can not reduce row-3 as all its elements are ∞.
We can not reduce row-4 as all its elements are ∞.
Column Reduction-
We can not reduce column-1 as all its elements are ∞.
We can not reduce column-2 as all its elements are ∞.
We can not reduce column-3 as all its elements are ∞.
We can not reduce column-4 as all its elements are ∞.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 139
and Analysis of Algorithm Unit 4
 Branch and Bound

Thus, the matrix is already column reduced.

Finally, the matrix is completely reduced.
All the entries have become ∞.
Now, we calculate the cost of node-7.

Cost(7)
= cost(6) + Sum of reduction elements + M[D,B]
= 25 + 0 + 0
= 25

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 140
and Analysis of Algorithm Unit 4
 Branch and Bound

Thus,
Optimal path is: A → C → D → B → A
Cost of Optimal path = 25 units.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 141
and Analysis of Algorithm Unit 4
 Branch and Bound

Travelling Salesman Problem- Example

Consider the following cost matrix

Here C(0,2)=30, C(4,0)=16, C(1,1)= Infinity ∞ and so on.

Below is the state space tree for the TSP , which shows optimal
solution marked in green
(https://www.techiedelight.com/travelling-salesman-problem-using-branch-and-
bound/)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 142
and Analysis of Algorithm Unit 4
 Branch and Bound

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 143
and Analysis of Algorithm Unit 4
 Branch and Bound

Travelling
. Salesman Problem- Steps

• As we can see from above diagram , every node has a cost associated
to it.

• When we go from city I to city j, cost of a node j will be sum of cost of

parent node I, cost of the edge (I,j) and lower bound of the path starting
at node j.

• As root node is the first node to be expanded , it doesn’t have any

parent. So cost will be only lower bound of the path starting at root.

• To get the lower bound of the path starting from the node , we reduce
each row and column in such a wat that there must be atleast one zero
in each row and column.
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 144
and Analysis of Algorithm Unit 4
 Branch and Bound

• . For doing this, we need to reduce the minimum value from each
element in each row and column.

Let’s start from root node

• We reduce the minimum value in each row from each element in that
row.
• Minimum in each row of cost matrix M is marked by blue[10,2,2,3,4]
below.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 145
and Analysis of Algorithm Unit 4
 Branch and Bound

• . After reducing the row, we get the below matrix. We then reduce
the minimum value in each column from each element in that
column.

• Minimum in each column is marked by blue[1 0 3 0 0]. After

reducing the column, we get below reduced matrix. This matrix
will be further processed by child nodes of root node to calculate
their lower bound.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 146
and Analysis of Algorithm Unit 4
 Branch and Bound

• The total expected cost at the root node is sum of all reductions.
• Cost=[10 2 2 3 4] + [1 0 3 0 0]= 25
• Since we have discovered the root node C0, the next node to be
expanded can be any node from C1,C2, C3, C4. Whichever node
has minimum cost, that node will be expanded further. So we have
to find out the expanding cost of each node.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 147
and Analysis of Algorithm Unit 4
 Branch and Bound

• The parent node (C0) has below reduced matrix-

.

• Let us consider edge from 0 1

1. As we are adding edge (0,1) to our search space, we get outgoing

edges for city 0 to infinity and all incoming edges to city 1 to
infinity. We also set (1,0) to infinity.

2. So in reduced matrix of parent node we change all the elements in

row 0 and column 1 and at index (1,0) to infinity(marked in red).

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 148
and Analysis of Algorithm Unit 4
 Branch and Bound

The resulting cost matrix is

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 149
and Analysis of Algorithm Unit 4
 Branch and Bound

3. We try to calculate lower bound of the path starting at node 1 using

above resulting cost matrix.

4. The lower bound is 0 as matrix is already in reduced form. i.e. all

rows and all columns have zero value.

Therefore for node 1, cost will be

Cost= cost of node 0 + cost of the edge (0,1) + lower bound of the
path starting at node 1
= 25 + 10 +0= 35

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 150
and Analysis of Algorithm Unit 4
 Branch and Bound

.Lets consider edge from 0 2

1. Change all the elements in row 0 and column 2 and at index(2,0) to

infinity(marked in red).

The resulting cost matrix is:

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 151
and Analysis of Algorithm Unit 4
 Branch and Bound

• Now calculate lower bound of the path starting at node 2 using the
Approach discussed earlier. Resulting matrix will be-

Therefore the cost of node 2, cost will be

Cost = Cost of node 0 + cost of the edge (0,2) + Lower bound of the
path starting at node 2
= 25 + 17 + 11= 53

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 152
and Analysis of Algorithm Unit 4
 Branch and Bound

Let us consider edge from 0 3

1. Change the elements in row 0 and column 3 and at index(3,0) to
Infinity(marked in red).

The Resulting cost matrix is :

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 153
and Analysis of Algorithm Unit 4
 Branch and Bound

• Now calculate lower bound of the path starting at node 3 using the
Approach discussed earlier.
• Lower bound of the path starting at node 3 is 0 as it is already in
reduced form, i.e. all rows and all columns have zero value.

Therefore for node 3, cost will be

Cost = Cost of node 0 + cost of the edge (0,3) + Lower bound of the
path starting at node 3
= 25 + 0 + 0= 25

Similarly we calculate for 0 4. Its cost will be 31.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 154
and Analysis of Algorithm Unit 4
 Branch and Bound

• Now we find a live node with estimated cost. Live nodes 1,2,3 and 4
has costs 35, 53, 25 and 31 respectively.

• The minimum among them is node 3 having cost 25. So node 3 will
be expanded further as shown in state space tree diagram.

• After adding its children to list of live nodes, we again find a live
node with least cost and expand it.

• We continue the search till a leaf is encountered in space search tree.

If a leaf is encountered, then the tour is completed and we will
return back to the root node.

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 155
and Analysis of Algorithm Unit 4
 Quiz

1. The problem of placing n queens in a chessboard such that no two

queens attack each other is called as________________.

2. ___________ enumerates a list of promising nodes that could be

computed to give the possible solutions of a given problem.

3. When dynamic programming is applied to a problem, it takes far

less time as compared to other methods that don’t take advantage
of overlapping subproblems.(True/False).

4. Branch and bound is a __________

5. Both LIFO branch and bound strategy and backtracking leads to

depth first search.(True/False)
Dr. Hirdesh Sharma BCS 503 Design
11/19/2024 156
and Analysis of Algorithm Unit 4
 Quiz

6. __________can traverse the state space tree only in DFS manner?

7. A node is said to be ____________ if it has a possibility of

reaching a complete solution.

8. A state-space tree for a backtracking algorithm is constructed using

______________________.

9. The leaves in a state-space tree represent only complete

solutions.(True / False)

10. Backtracking algorithm is faster than the brute force

technique(True/ False)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 157
and Analysis of Algorithm Unit 4
 Weekly Assignment

1. Explain Floyd algorithm and also analyze its complexity. [CO4]

2. What is nQueens problem? Write the steps for solving the nQueens
problem. [CO4]
3. Explain Graph colouring Problem with the help of suitable example.
[CO4]
4. Find the optimal solution to the knapsack 0/1 instances n=7,m=15.
(V1,V2,V3,V4,V5,V6,V7)=(10,5,15,7,6,18,3)
(W1,W2,W3,W4,W5,W6,W7 )=(2,3,5,7,1,4,1) [CO4]
5. Let S={4,6,7,8} and m=18. Find all possible subsets of S that sums to m.
Draw state space tree that is generated. [CO4]
6. Use Floyd Warshall algorithm to find shortest path for all of the vertices
of the given graph. Give the complexity of the algorithm.
[CO4]

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 158
and Analysis of Algorithm Unit 4
 Weekly Assignment

6. Consider following instance for simple Knapsack Problem. Find the

solution using greedy method. N:8, Value of knapsack is 110.
V : { 30,20,100,90,160,200,180,220}
W : {5, 10, 20,22,33, 43, 45, 55} [CO4]

7. Write short note on Branch and Bound Technique. [CO4]

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 159
and Analysis of Algorithm Unit 4
 MCQ

1. Which of the following is/are property/properties of a dynamic

programming problem?
a) Optimal substructure
b) Overlapping subproblems
c) Greedy approach
d) Both optimal substructure and overlapping subproblems

2. If a problem can be broken into subproblems which are reused

several times, the problem possesses ____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 160
and Analysis of Algorithm Unit 4
 MCQ

3. When dynamic programming is applied to a problem, it takes far

less time as compared to other methods that don’t take advantage
of overlapping subproblems.
a) True
b) False

4. Which of the following problems is NOT solved using dynamic

programming?
a) 0/1 knapsack problem
b) Matrix chain multiplication problem
c) Edit distance problem
d) Fractional knapsack problem

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 161
and Analysis of Algorithm Unit 4
 MCQ

5. Which of the following problems should be solved using dynamic

programming?
a) Mergesort
b) Binary search
c) Longest common subsequence
d) Quicksort

6. If a problem can be solved by combining optimal solutions to non-

overlapping problems, the strategy is called _____________
a) Dynamic programming
b) Greedy
c) Divide and conquer
d) Recursion

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 162
and Analysis of Algorithm Unit 4
 MCQ

7. Which of the problems cannot be solved by backtracking method?

a) n-queen problem
b) subset sum problem
c) hamiltonian circuit problem
d) travelling salesman problem

8. Backtracking algorithm is implemented by constructing a tree of

choices called as?
a) State-space tree
b) State-chart tree
c) Node tree
d) Backtracking tree

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 163
and Analysis of Algorithm Unit 4
 MCQ

9. In what manner is a state-space tree for a backtracking algorithm

constructed?
a) Depth-first search
b) Breadth-first search
c) Twice around the tree
d) Nearest neighbour first

10. The problem of finding a subset of positive integers whose sum is

equal to a given positive integer is called as?
a) n- queen problem
b) subset sum problem
c) knapsack problem
d) hamiltonian circuit problem

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 164
and Analysis of Algorithm Unit 4
 Glossary Question

Q.1The 0/1 Knapsack problem is an example of ____________

a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer
Q.2 __________method can be used to solve the Knapsack problem?
a) Brute force algorithm
b) Recursion
c) Dynamic programming
d) Brute force, Recursion and Dynamic Programming

Q.3 ______ is used to solve the matrix chain multiplication problem?

a) Dynamic programming
b) Brute force
c) Recursion
d) Dynamic Programming, Brute force, Recursion

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 165
and Analysis of Algorithm Unit 4
 Glossary Question

Q.4 ________ problems can be solved using the longest subsequence problem?
a) Longest increasing subsequence
b) Longest palindromic subsequence
c) Longest bitonic subsequence
d) Longest decreasing subsequence
Q.5 ___________is the worst case time complexity of dynamic programming solution
of the subset sum problem(sum=given subset sum)?
a) O(n)
b) O(sum)
c) O(n2)
d) O(sum*n)
Q.6 In ______ directions queens attack each other?
a) 1
b) 2
c) 3
d) 4

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 166
and Analysis of Algorithm Unit 4
 Glossary Question

Q.7 Placing n-queens so that no two queens attack each other is called__________
a) n-queen’s problem
b) 8-queen’s problem
c) Hamiltonian circuit problem
d) subset sum problem

Q.8 The n-queens problem implemented in _________.

a) carom
b) chess
c) ludo
d) cards
Q.9 __________methods can be used to solve n-queen’s problem.
a) greedy algorithm
b) divide and conquer
c) iterative improvement
d) backtracking

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 167
and Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 168
and Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 169
and Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 170
and Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 171
and Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 172
and Analysis of Algorithm Unit 4
 Old Question Papers(2020-2021)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 173
and Analysis of Algorithm Unit 4
 Old Question Papers(2020-2021)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 174
and Analysis of Algorithm Unit 4
 Old Question Papers(2020-2021)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 175
and Analysis of Algorithm Unit 4
 Old Question Papers(2020-2021)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 176
and Analysis of Algorithm Unit 4
 Old Question Papers(2020-2021)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 177
and Analysis of Algorithm Unit 4
 Old Question Papers(2019-2020)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 178
and Analysis of Algorithm Unit 4
 Old Question Papers(2019-2020)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 179
and Analysis of Algorithm Unit 4
 Old Question Papers(2019-2020)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 180
and Analysis of Algorithm Unit 4
 Old Question Papers(2019-2020)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 181
and Analysis of Algorithm Unit 4
 Old Question Papers(2019-2020)

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 182
and Analysis of Algorithm Unit 4
 Expected Questions for University Exam

1. Solve the problem of travelling salesman problem on

following graph and perform operation for each vertex.
[CO4]

2. Write Short notes on the following. [CO4]

i) Graph Coloring
ii)Sub Set Sum Problem
iii)Hamiltonian Cycle

Dr. Hirdesh Sharma BCS 503 Design

11/19/2024 183
and Analysis of Algorithm Unit 4
 Expected Questions for University Exam

3. Find out one optimal solution for following using back

tracking.
4*4 chessboard,4 Queen Problem
8*8 chessboard,8 Queen Problem
[CO4]

4. Write the difference between the Greedy method and

Dynamic programming.
[CO4]

5. Explain the term state space search tree with suitable

example.
[CO4]

6. Explain Floyd algorithm and also analyze its complexity

[CO4]
11/19/2024
Dr. Hirdesh Sharma BCS 503 Design
184
and Analysis of Algorithm Unit 4
 Recap of Unit

This unit gives the insights of different techniques like

Dynamic Programming, Back tracking and Branch and Bound .
Different real world problem have been solved with these
approaches.
The problems discussed here are Travelling salesman Problem,
n Queens problem , Sum of subsets problem, Floyd Warshall
algorithm, Knapsack Problem, Graph Colouring and
Hamiltonion Cycle.

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 185
 Thank You

11/19/2024 Dr. Hirdesh Sharma BCS 503 Design and Analysis of Algorithm Unit 4 186