Noida Institute of Engineering and Technology, Greater

Noida

UNIT 4
Dynamic Programming, Backtracking and
Branch and Bound

Design & Analysis of Algorithms

Dr. Amba Mishra
ACSE0501
Associate Professor
B.Tech 5th Sem IT Deptt.

Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 1

12/24/2024
 Evaluation Scheme

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 2
 Syllabus

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 3
 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. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4

12/24/2024 4
 Course Outcome

At the end of the semester, the student will be able:

Description Bloom’s Taxonomy
CO To have knowledge of basic principles of algorithm design and Knowledge, analysis
1 Analysis, asymptotic notations and growth of functions for time And design
and space complexity analysis and applying the same in different
sorting algorithms
CO To apply different problem-solving approaches for advanced Knowledge, analysis
2 data structures And apply
CO To apply divide and conquer method for solving merge sort, Knowledge, analysis and
3 quick sort, matrix multiplication and Greedy Algorithm for Apply
solving different Graph Problem.

CO To analyze and apply different optimization techniques like Knowledge, Analysis And
4 dynamic programming, backtracking and Branch & Bound to Apply
solve the complex problems
CO To understand the advanced concepts like NP Completeness and Knowledge, Analysis and
5 Fast Fourier Transform, to analyze and apply String Matching, Apply
Approximation and Randomized Algorithms to solve the
complex problems

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 5
 Program Outcome

At the end of the semester, the student will be able:

POs Engineering Graduates will be able to
PO1 Engineering Knowledge
PO2 Problem Analysis
PO3 Design & Development of solutions
PO4 Conduct Investigation of complex problems
PO5 Modern Tool Usage
PO6 The Engineer and Society
PO7 Environment and sustainability
PO8 Ethics
PO9 Individual & Team work
PO10 Communication
PO11 Project management and Finance
PO12 Life Long Learning

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 6
 CO-PO and PSO Mapping

Design and Analysis of Algorithm (ACSE-502)

PO1
CO.K PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO12
1

ACSE0501.1 3 3 3 3 2 - - - 2 2 - 3

ACSE0501.2 3 3 3 3 2 2 - 1 1 1 - 3

ACSE0501.3 3 3 2 3 3 2 - 2 1 1 2 3

ACSE0501.4 3 3 3 3 2 2 - 2 2 1 3 3

ACSE0501.5 2 2 2 2 2 2 - 2 1 1 1 2

Average 2.8 2.8 2.6 2.8 2.2 1.6 - 1.8 1.4 1.2 1.2 2.8

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 7
 Program Educational Objectives(PEOs)

PEO1: To have an excellent scientific and engineering breadth so as to

comprehend, analyze, design and provide sustainable solutions for
real-life problems using state-of-the-art technologies.
PEO2:To have a successful career in industries, to pursue higher studies or
to support entrepreneurial endeavors and to face global challenges.
PEO3:To have an effective communication skills, professional attitude,
ethical values and a desire to learn specific knowledge in emerging
trends, technologies for research, innovation and product
development and contribution to society.
PEO4: To have life-long learning for up-skilling and re-skilling for
successful professional career as engineer, scientist, enterpreneur
and bureaucrat for betterment of society

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 8
 End Semester Question Paper Template

B TECH
(SEM-IV) THEORY EXAMINATION 20__-20__
COMPILER DESIGN
Time: 3 Hours Total
Marks: 100
Note: 1. Attempt all Sections. If require any missing data; then choose
suitably.
SECTION A
1.Q.No.
Attempt all questions in brief.
Question Marks 2 xCO10 =
20
1 2
2 2
. .
10 2

12/24/2024 9
Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4
 End Semester Question Paper Template

SECTION B
2. Attempt any three of the following: 3 x 10 = 30

Q.No. Question Mark CO

s
1 10
2 10
. .
5 SECTION C 10
3. Attempt any one part of the following: 1 x 10 = 10

Q.No. Question Marks CO

1 10
2 10
Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 10
4
 End Semester Question Paper Template

4. Attempt any one part of the following: 1 x 10 = 10

Q.No. Question Marks CO

1 10
2 10
5. Attempt any one part of the following: 1 x 10 = 10
Q.No. Question Marks CO
1 10
2 10
6. Attempt any one part of the following: 1 x 10 = 10
Q.No. Question Mark CO
s

1 10
2 10

Dr. Amba Mishra ACSE0501 Design and Analysis of

12/24/2024 11
Algorithm Unit 4
 Prerequisite and Recap

• Prerequisite
• Basic concept of c programming language.
• Concept of stack, queue and link list.

• Recap
• Flow Chart
• Algorithm

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 12
 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. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4

12/24/2024 13
 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
12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 14
 Unit Objective

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

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 15
 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 16
 Dynamic Programming

• 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
12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 17
 Dynamic Programming

Examples of Dynamic Programming (DP)

Example 1: Consider the problem of finding the
Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21…

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 18
 Dynamic Programming

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 19
 Dynamic Programming

So for finding fib (5 ) it makes total 15 calls.

To Prepare a recurrecnce relation assume fib(n-2) as
fib(n-1) only . (**we take it so that we come to the
conclusion, so we take upper bound of function )
T(n)=2T(n-1) + 1

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 20
 Dynamic Programming

several sub-problems like fib(4), fib(3), fib(2),

and so on can be seen occurring multiple times.
We can reduce the function calls .
We’ll take global array and initially trace this
with-1-1 -1F -1 -1 -1 -1
0 1 2 3 4 5
Let’s trace tree once again , first function is fib(5) we
don’t know as it is -1 so make the calls ,next we get
fib(3) we don’t know as it is -1 so , fib(1) is -1 so check
what is value wen n=1 ,the value is 1.
12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 21
 Dynamic Programming

0 1 -1 -1 -1 -1
F
0 1 2 3 4 5
Now in series check fib(2) we don’t know value as it is -1,
check next fib(0) its value is 0. Then fib(1) we all know value
of fib(1) is 1 so don’t call the this function again.
Now fib(0) + fib(1) and return result fib(2) it becomes 1.
0 1 1
F
0 1 2 3 4 5

Now check for fib(4) and for that check fib(2) and fib(3) but
don’t call them as they already have values so wen they are not
called otherDr.also
12/24/2024 not ACSE0501
Amba Mishra called .Design and Analysis of Algorithm Unit 4 22
 Dynamic Programming

f 0 1 1 2 3 5

It makes n+1 calls for fib(n) it takes O (n) times , this is

memoization
12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 23
 Dynamic Programming

Using Dynamic Programming approach with memoization:

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 24
 Dynamic Programming

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 25
 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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 26
 Dynamic Programming

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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 27
 Dynamic Programming

All Pair Shortest Path(Floyd-Warshall algorithm)

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 28
 Dynamic Programming

All Pair Shortest Path(Floyd-Warshall algorithm)

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 29
 Dynamic Programming

All Pair Shortest Path(Floyd-Warshall algorithm)

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 30
 Dynamic Programming

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 31
 Dynamic Programming

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 ]

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 32
 Dynamic Programming

• 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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 33
 Practice Question

Q.1 Consider the following directed weighted graph-

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 34
 Dynamic Programming

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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 35

nd Analysis of Algorithm Unit 4
 Dynamic Programming

Dr. Amba Mishra ACSE0501 Design and Analysis of

12/24/2024 36
Algorithm Unit 4
 Dynamic Programming

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 37

nd Analysis of Algorithm Unit 4
 Dynamic Programming

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 38

nd Analysis of Algorithm Unit 4
 Dynamic Programming

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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 39

nd Analysis of Algorithm Unit 4
 Dynamic Programming
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?

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 40
 Dynamic Programming

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 41
 Dynamic Programming

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 42
 Dynamic Programming

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) ,…..

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 43
 Dynamic Programming

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>

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 44

nd Analysis of Algorithm Unit 4
 Dynamic Programming

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]

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 45

nd Analysis of Algorithm Unit 4
 Dynamic Programming

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 46

nd Analysis of Algorithm Unit 4
 Dynamic Programming

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 47

nd Analysis of Algorithm Unit 4
 Dynamic Programming

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 48

nd Analysis of Algorithm Unit 4
 Dynamic Programming

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 49

nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

• 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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 50
nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

• 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}…

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 51

nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 52

nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

Using Dynamic Programming to find the LCS

• Let us take two sequences:

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 53

nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 54

nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

2. Fill each cell of the table using the following

logic.
3. If the character correspoding 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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 55
nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 56

nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 57

nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

6. The value in the last row and the last

column is the length of the longest common
subsequence.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 58

nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

• 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 59
nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 60
nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence

• 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)
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 61
nd Analysis of Algorithm Unit 4
 Longest Common Sub Sequence
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])

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 62

nd Analysis of Algorithm Unit 4
 Dynamic Programming

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)}

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 63

nd Analysis of Algorithm Unit 4
 Dynamic Programming

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, 0i≤ n-1, represents project I, there are m+1 vertices,
associated with stage i, 1i≤ 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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 64
nd Analysis of Algorithm Unit 4
 Dynamic Programming

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)}

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 65

nd Analysis of Algorithm Unit 4
 Dynamic Programming

• 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 66

nd Analysis of Algorithm Unit 4
 Dynamic Programming

• 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 67

nd Analysis of Algorithm Unit 4
 Dynamic Programming

• 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 68

nd Analysis of Algorithm Unit 4
 Dynamic Programming

• 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 69

nd 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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 70
nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 71

nd 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 needDr.some
12/24/2024
formula.
Amba Mishra ACSE0501 Design a 72
nd 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
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 73
nd 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. Amba Mishra ACSE0501 Design and Analysis of Algorithm
12/24/2024 74
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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 75

nd 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
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 76
nd 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 this we understand that we
12/24/2024
will start finding from smallDr. Amba Mishra ACSE0501 Design a
ndvalues.
Analysis of Algorithm Unit 4
77
 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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 78

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 79

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 80

nd Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 81

nd Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 82

nd Analysis of Algorithm Unit 4
 Matrix Chain Multiplication

On continuing this we get

Here number of scalar multiplication is 58

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 83

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 84

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 85
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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 86

nd 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
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 87
nd 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 “)”

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 88

nd Analysis of Algorithm Unit 4
 BFS and DFS

Every tree is graph. In graph we traverse each

node either using BFS or DFS.
BFS : In BFS, one vertex is selected at a time
when it is visited and marked then its adjacent are
visited and stored in the queue. It is slower than
DFS. It uses a Queue data structure that follows
first in first out.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 89

nd Analysis of Algorithm Unit 4
 BFS and DFS

DFS : It uses the Stack data structure and

performs two stages, first visited vertices are
pushed into the stack, and second if there are no
vertices then visited vertices are popped.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 90

nd Analysis of Algorithm Unit 4
 BFS and DFS

As we can see Backtracking can be done in DFS

not in BFS.
**wen deadend occurs then we do backtracking*

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 91

nd Analysis of Algorithm Unit 4
 BFS and DFS

Breadth-First Search (BFS) and Depth-First Search

(DFS) are two fundamental algorithms used for
traversing or searching graphs and trees. This article
covers the basic difference between Breadth-First Search
and Depth-First Search.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 92

nd Analysis of Algorithm Unit 4
 BFS and DFS

• How does DFS work?

Depth-first search is an algorithm for traversing
or searching tree or graph data structures. The
algorithm starts at the root node (selecting some
arbitrary node as the root node in the case of a
graph) and explores as far as possible along each
branch before backtracking.

Let us understand the working of Depth First

Search with the help of the following illustration:
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 93
nd Analysis of Algorithm Unit 4
 BFS and DFS

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 94

nd Analysis of Algorithm Unit 4
 BFS and DFS

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 95

nd Analysis of Algorithm Unit 4
 BFS and DFS

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 96

nd Analysis of Algorithm Unit 4
 BFS and DFS

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 97

nd Analysis of Algorithm Unit 4
 BFS and DFS

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 98

nd Analysis of Algorithm Unit 4
 BFS and DFS

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 99

nd Analysis of Algorithm Unit 4
 Backtracking - Objective

This objective of this topic is to make students understand

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 100

nd Analysis of Algorithm Unit 4
 Prerequisite and Recap

• Prerequisite
• Algorithms Concepts
• C programming
• Graph

• Recap
• Dynamic Programming

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 101

nd Analysis of Algorithm Unit 4
 Backtracking

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 102
nd Analysis of Algorithm Unit 4
 Backtracking

Example :

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 103

nd Analysis of Algorithm Unit 4
 Backtracking

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 104

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 105

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 106

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 107

nd Analysis of Algorithm Unit 4
 Backtracking

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 108

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 109

nd 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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design a
nd Analysis of Algorithm Unit 4
110
 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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 111

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 112

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 113

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 114

nd 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).

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 115

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 116

nd 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."

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 117

nd 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 q 2 in column 3, i.e. (2, 3) but
then no position is left for placing queen 'q 3' safely.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 118

nd Analysis of Algorithm Unit 4
 N - Queens Problem

N- Queens Problem

• So we backtrack one step and place the queen 'q 2' 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).

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 119

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 120

nd Analysis of Algorithm Unit 4
 N - Queens Problem

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 121

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 122

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 123

nd Analysis of Algorithm Unit 4
 N - Queens Problem

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 124

nd 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|
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 125
nd 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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 126
 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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 127

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 128

nd Analysis of Algorithm Unit 4
 Sum of Subsets Problem

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 129

nd Analysis of Algorithm Unit 4
 Sum of Subsets Problem

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 130

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 131

nd Analysis of Algorithm Unit 4
 Sum of Subsets Problem

Sum of Subsets Algorithm

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 132

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 133

nd Analysis of Algorithm Unit 4
 Sum of Subsets Problem

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}

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 134

nd Analysis of Algorithm Unit 4
 Branch and Bound - Objective

This objective of this topic is to make students understand

about
• Concepts of Branch and Bound
• Travelling Salesman Problem

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 135
 Prerequisite and Recap

• Prerequisite
• Algorithms Concepts
• C programming
• Graph

• Recap
• Backtracking

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 136
 Branch and Bound

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 137

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 138

nd 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).

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 139

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 140

nd Analysis of Algorithm Unit 4
 Branch and Bound

Travelling Salesman Problem- Example

The initial cost matrix is :

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 141

nd Analysis of Algorithm Unit 4
 Branch
Branchand
ad Bound
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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 142

nd 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. Amba Mishra ACSE0501 Design
12/24/2024 143
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. Amba Mishra ACSE0501 Design
12/24/2024 144
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. Amba Mishra ACSE0501 Design

12/24/2024 145
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 ∞

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

Dr. Amba Mishra ACSE0501 Design

12/24/2024 146
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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 147
 Branch and Bound

we obtain the following row-reduced matrix-

Dr. Amba Mishra ACSE0501 Design

12/24/2024 148
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. Amba Mishra ACSE0501 Design

12/24/2024 149
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 ∞
• Set M[C,A] = ∞ Dr. Amba Mishra ACSE0501 Design
12/24/2024 150
and Analysis of Algorithm Unit 4
 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. Amba Mishra ACSE0501 Design
12/24/2024 151
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]
= 18 + 0 + 7 = 25 Dr. Amba Mishra ACSE0501 Design
12/24/2024 152
and Analysis of Algorithm Unit 4
 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. Amba Mishra ACSE0501 Design

12/24/2024 153
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. Amba Mishra ACSE0501 Design

12/24/2024 154
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. Amba Mishra ACSE0501 Design
12/24/2024 155
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. Amba Mishra ACSE0501 Design

12/24/2024 156
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. Amba Mishra ACSE0501 Design

12/24/2024 157
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. Amba Mishra ACSE0501 Design

12/24/2024 158
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. Amba Mishra ACSE0501 Design

12/24/2024 159
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. Amba Mishra ACSE0501 Design
12/24/2024 160
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. Amba Mishra ACSE0501 Design

12/24/2024 161
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. Amba Mishra ACSE0501 Design

12/24/2024 162
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. Amba Mishra ACSE0501 Design

12/24/2024 163
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. Amba Mishra ACSE0501 Design

12/24/2024 164
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. Amba Mishra ACSE0501 Design

12/24/2024 165
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. Amba Mishra ACSE0501 Design

12/24/2024 166
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. Amba Mishra ACSE0501 Design

12/24/2024 167
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. Amba Mishra ACSE0501 Design

12/24/2024 168
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. Amba Mishra ACSE0501 Design

12/24/2024 169
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)= 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/
)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 170

nd Analysis of Algorithm Unit 4
 Branch and Bound

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 171

nd 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.
12/24/2024 Dr. Amba Mishra ACSE0501 Design a 172
nd 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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 173

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 174

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 175

nd 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).

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 176

nd Analysis of Algorithm Unit 4
 Branch and Bound

The resulting cost matrix is

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 177

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 178

nd 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:

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 179

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 180

nd 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 :

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 181

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 182

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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 183

nd Analysis of Algorithm Unit 4
 Faculty Video Links, Youtube & NPTEL Video Links and Online Courses Details
Branch and Bound - Objective

• Youtube/other Video Links

• https://www.youtube.com/watch?v=oNI0rf2P9gE
• https://www.youtube.com/watch?v=9iE9Mj4m8jk
• https://www.youtube.com/watch?v=kyLxTdsT8ws
• https://nptel.ac.in/courses/106106133/

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 184

nd 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)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 185

nd 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)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 186

nd 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]

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 187

nd 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]

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 188

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 189

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 190

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 191

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 192

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 193

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 194

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 195

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 196

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 197

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 198

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 199

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 200

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 201

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 202

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 203

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 204

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 205

nd Analysis of Algorithm Unit 4
 Old Question Papers(2021-2022)

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 206
 Old Question Papers

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 207

nd Analysis of Algorithm Unit 4
 Old Question Papers

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 208

nd Analysis of Algorithm Unit 4
 Old Question Papers

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 209

nd Analysis of Algorithm Unit 4
 Old Question Papers

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 210

nd Analysis of Algorithm Unit 4
 Old Question Papers

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 211

nd 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

12/24/2024 Dr. Amba Mishra ACSE0501 Design a 212

nd 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]
12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 213
 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.

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 214
 Unit-4

Thank You

12/24/2024 Dr. Amba Mishra ACSE0501 Design and Analysis of Algorithm Unit 4 215