BCS503 - DAA Unit-4 AKTU

DESIGN AND ANALYSIS OF

ALGORITHMS
BCS503 - Unit-4
AKTU University - 5th Semester

AcademicArk
https://academicark-mvp8.onrender.com/

Dynamic Programming & Advanced Algorithm Techniques

Contents
1 Dynamic Programming 4
rk

1.1 Key Principles of Dynamic Programming . . . . . . . . . . . . . . . . . . 4

ica

1.1.1 1. Optimal Substructure . . . . . . . . . . . . . . . . . . . . . . . 4

m

1.1.2 2. Overlapping Subproblems . . . . . . . . . . . . . . . . . . . . . 4

e

1.2 Dynamic Programming Approaches . . . . . . . . . . . . . . . . . . . . . 4

ad
ac

2 0/1 Knapsack Problem 5

2.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Dynamic Programming Approach . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 State Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.2 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Time and Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Space-Optimized Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 All Pairs Shortest Paths 7

3.1 Floyd-Warshall Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1 Algorithm Principle . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.2 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Time and Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Warshall’s Algorithm (Transitive Closure) . . . . . . . . . . . . . . . . . 9
3.4.1 Transitive Closure Definition . . . . . . . . . . . . . . . . . . . . . 9

4 Resource Allocation Problem 10

4.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Dynamic Programming Approach . . . . . . . . . . . . . . . . . . . . . . 10
4.2.1 State Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2.2 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . 10

1 academicark
BCS503 - DAA Unit-4 AKTU

4.2.3 Boundary Conditions . . . . . . . . . . . . . . . . . . . . . . . . . 10

5 Backtracking 12
5.1 General Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Key Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

6 N-Queens Problem 13
6.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.3 Backtracking Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.4 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

7 Graph Coloring Problem 16

7.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.2 Backtracking Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

8 Hamiltonian Cycle Problem 18

8.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.2 Backtracking Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

9 Sum of Subsets Problem 20

9.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
9.2 Backtracking Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
rk

9.3 Pruning Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

ica

10 Branch and Bound 22

e m

10.1 Key Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

ad

10.2 Differences from Backtracking . . . . . . . . . . . . . . . . . . . . . . . . 22

ac

10.3 General Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

11 Travelling Salesman Problem (TSP) 24

11.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
11.2 Branch and Bound Approach . . . . . . . . . . . . . . . . . . . . . . . . 24
11.2.1 Cost Matrix Reduction . . . . . . . . . . . . . . . . . . . . . . . . 24
11.2.2 Bounding Function . . . . . . . . . . . . . . . . . . . . . . . . . . 24
11.3 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
11.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

12 0/1 Knapsack using Branch and Bound 26

12.1 Bounding Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
12.1.1 Upper Bound Calculation . . . . . . . . . . . . . . . . . . . . . . 26

13 Comparison: Backtracking vs Branch and Bound 28

13.1 Detailed Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
13.2 When to Use Which? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

14 Summary and Key Takeaways 29

14.1 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
14.2 All Pairs Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
14.3 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2 academicark
BCS503 - DAA Unit-4 AKTU

14.4 Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

14.5 Problem Selection Guidelines . . . . . . . . . . . . . . . . . . . . . . . . 29

15 Important Formulas and Complexities 30

15.1 Time Complexities Summary . . . . . . . . . . . . . . . . . . . . . . . . 30
15.2 Key Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . 30
15.2.1 0/1 Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
15.2.2 Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
15.2.3 Resource Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . 30

16 Practice Problems 31
16.1 Problem 1: Modified Knapsack . . . . . . . . . . . . . . . . . . . . . . . 31
16.2 Problem 2: Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . 31
16.3 Problem 3: N-Queens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
16.4 Problem 4: TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
16.5 Problem 5: Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . 31
16.6 Problem 6: Sum of Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . 31
16.7 Problem 7: Resource Allocation . . . . . . . . . . . . . . . . . . . . . . . 31

17 Exam Tips and Important Points 32

17.1 Common Mistakes to Avoid . . . . . . . . . . . . . . . . . . . . . . . . . 32
17.2 Quick Revision Checklist . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
rk
ica
e m
ad
ac

3 academicark
BCS503 - DAA Unit-4 AKTU

1 Dynamic Programming
Definition
Dynamic Programming is an algorithmic paradigm that solves complex prob-
lems by breaking them down into simpler subproblems and storing the results of
subproblems to avoid redundant computations. It is particularly useful when the
problem exhibits overlapping subproblems and optimal substructure properties.

1.1 Key Principles of Dynamic Programming

1.1.1 1. Optimal Substructure
An optimal solution to the problem contains optimal solutions to its subproblems.

1.1.2 2. Overlapping Subproblems

The same subproblems are solved multiple times, making it beneficial to store their
solutions.

1.2 Dynamic Programming Approaches

Important Note
rk
ica

Dynamic Programming can be implemented using two main approaches:

m

1. Top-Down Approach (Memoization): Solve the problem recursively and

e
ad

store results.
ac

2. Bottom-Up Approach (Tabulation): Solve smaller subproblems first and

build up to the solution.

4 academicark
BCS503 - DAA Unit-4 AKTU

2 0/1 Knapsack Problem

2.1 Problem Statement
Definition
Given:

• n items, each with weight wi and value vi

• A knapsack with capacity W

Objective: Maximize the total value of items in the knapsack without exceeding
its capacity, where each item can be either included (1) or excluded (0).

2.2 Dynamic Programming Approach

2.2.1 State Definition
Let dp[i][w] represent the maximum value that can be obtained using the first i items
with a knapsack capacity of w.

2.2.2 Recurrence Relation

rk


0
 if i = 0 or w = 0
ica

dp[i][w] = dp[i − 1][w] if wi > w

m


max(dp[i − 1][w], vi + dp[i − 1][w − wi ]) if wi ≤ w

e
ad

Algorithm
ac

0/1 Knapsack Algorithm:

1: procedure Knapsack(W, wt[], val[], n)
2: Initialize dp[n + 1][W + 1] with zeros
3: for i ← 1 to n do
4: for w ← 1 to W do
5: if wt[i − 1] ≤ w then
6: dp[i][w] ← max(val[i − 1] + dp[i − 1][w − wt[i − 1]], dp[i − 1][w])
7: else
8: dp[i][w] ← dp[i − 1][w]
9: end if
10: end for
11: end for
12: return dp[n][W ]
13: end procedure

5 academicark
BCS503 - DAA Unit-4 AKTU

Example

Example: 0/1 Knapsack Problem

Given:

• Items: {(weight=2, value=3), (weight=3, value=4), (weight=4, value=5),

(weight=5, value=6)}

• Knapsack Capacity: W = 5 kg

Solution Using Dynamic Programming:

Step 1: Create DP table dp[5][6]

Item/Weight 0 1 2 3 4 5
0 (No items) 0 0 0 0 0 0
1 (w=2, v=3) 0 0 3 3 3 3
2 (w=3, v=4) 0 0 3 4 4 7
3 (w=4, v=5) 0 0 3 4 5 7
4 (w=5, v=6) 0 0 3 4 5 7

Optimal Solution: Maximum value = 7 (Items 1 and 2)

rk

2.3 Time and Space Complexity

ica

Important Note
e m

• Time Complexity: O(n × W ) - pseudo-polynomial

ad
ac

• Space Complexity: O(n × W ) - can be optimized to O(W )

2.4 Space-Optimized Approach

Since dp[i][w] only depends on dp[i − 1][w], we can use a 1D array:

Algorithm

1: procedure KnapsackOptimized(W, wt[], val[], n)

2: Initialize dp[W + 1] with zeros
3: for i ← 1 to n do
4: for w ← W down to wt[i − 1] do ▷ Traverse backwards
5: dp[w] ← max(dp[w], val[i − 1] + dp[w − wt[i − 1]])
6: end for
7: end for
8: return dp[W ]
9: end procedure

6 academicark
BCS503 - DAA Unit-4 AKTU

3 All Pairs Shortest Paths

3.1 Floyd-Warshall Algorithm
Definition
Floyd-Warshall Algorithm finds the shortest paths between all pairs of vertices
in a weighted directed graph. It works with both positive and negative edge weights
(but no negative cycles).

3.1.1 Algorithm Principle

The algorithm considers all vertices as intermediate vertices and checks if path through
vertex k provides a shorter path between vertices i and j.

3.1.2 Recurrence Relation

dist[i][j](k) = min(dist[i][j](k−1) , dist[i][k](k−1) + dist[k][j](k−1) )
where dist[i][j](k) is the shortest distance from i to j using vertices {1, 2, . . . , k} as
intermediate vertices.

Algorithm
rk

Floyd-Warshall Algorithm:
ica

1: procedure FloydWarshall(graph[][], n)
m

2: Initialize dist[][] ← graph[][]

e

3: for i ← 1 to n do
ad

4: dist[i][i] ← 0
ac

5: end for
6: for k ← 1 to n do ▷ Intermediate vertex
7: for i ← 1 to n do ▷ Source vertex
8: for j ← 1 to n do ▷ Destination vertex
9: if dist[i][k] ̸= ∞ AND dist[k][j] ̸= ∞ then
10: dist[i][j] ← min(dist[i][j], dist[i][k] + dist[k][j])
11: end if
12: end for
13: end for
14: end for
15: return dist[][]
16: end procedure

7 academicark
BCS503 - DAA Unit-4 AKTU

Example
Example: Floyd-Warshall Algorithm
Consider a graph with 4 vertices and the following adjacency matrix:
Initial Distance Matrix:
1 2 3 4
1 0 4 ∞ 5
2 ∞ 0 1 ∞
3 2 ∞ 0 3
4 ∞ ∞ 1 0

After applying Floyd-Warshall (Final Distance Matrix):

1 2 3 4
1 0 4 5 5
2 3 0 1 4
3 2 6 0 3
4 3 7 1 0

3.2 Time and Space Complexity

rk

Important Note
ica

• Time Complexity: O(n3 )

m

• Space Complexity: O(n2 )

e
ad
ac

3.3 Applications
• Network routing protocols

• Finding transitive closure

• Detection of negative cycles

• Computing graph diameter

8 academicark
BCS503 - DAA Unit-4 AKTU

3.4 Warshall’s Algorithm (Transitive Closure)

Definition
Warshall’s Algorithm computes the transitive closure of a directed graph, de-
termining reachability between all pairs of vertices.

3.4.1 Transitive Closure Definition

The transitive closure of a graph G = (V, E) is a graph G∗ = (V, E ∗ ) where (i, j) ∈ E ∗ if
and only if there exists a path from vertex i to vertex j in G.

Algorithm
Warshall’s Algorithm:
1: procedure Warshall(adjM atrix[][], n)
2: Initialize reach[][] ← adjM atrix[][]
3: for i ← 1 to n do
4: reach[i][i] ← 1 ▷ Vertex reachable to itself
5: end for
6: for k ← 1 to n do ▷ Intermediate vertex
7: for i ← 1 to n do
8: for j ← 1 to n do
rk

9: reach[i][j] ← reach[i][j] OR (reach[i][k] AND reach[k][j])

ica

10: end for

m

11: end for

e

12: end for

ad

13: return reach[][]

ac

14: end procedure

Example
Example: Warshall’s Algorithm
Given directed graph with adjacency matrix:
Initial Adjacency Matrix:
1 2 3 4
1 1 1 0 0
2 0 1 1 0
3 0 0 1 1
4 0 0 0 1

Transitive Closure Matrix:

1 2 3 4
1 1 1 1 1
2 0 1 1 1
3 0 0 1 1
4 0 0 0 1

9 academicark
BCS503 - DAA Unit-4 AKTU

4 Resource Allocation Problem

Definition
Resource Allocation Problem involves distributing limited resources among
competing activities to maximize total return or minimize total cost.

4.1 Problem Formulation

Given:
• X units of resource available
• N activities requiring resources
• Return function ri (x): return from activity i when allocated x units
Objective: Maximize total return N
P PN
i=1 ri (xi ) subject to i=1 xi ≤ X

4.2 Dynamic Programming Approach

4.2.1 State Definition
Let Sk (x) = maximum return obtainable from activities k through N with x units of
resource remaining.
rk
ica

4.2.2 Recurrence Relation

e m

Sk (x) = max {rk (j) + Sk+1 (x − j)}

ad

j=0,1,...,x
ac

4.2.3 Boundary Conditions

• SN (x) = rN (x) for all x
• Sk (0) = 0 for all k

Example
Example: Resource Allocation Problem
Suppose 4 doctors are to be allocated to 3 hospitals. The table shows patients
served per hour:

Doctors Hospital 1 Hospital 2 Hospital 3

0 0 0 0
1 4 2 5
2 6 4 7
3 9 7 8
4 10 11 9

Solution using Dynamic Programming:

Stage 3 (Hospital 3): S3 (x) = r3 (x): {0, 5, 7, 8, 9}
Stage 2 (Hospital 2): For each x, compute S2 (x) = maxj {r2 (j) + S3 (x − j)}

10 academicark
BCS503 - DAA Unit-4 AKTU

Stage 1 (Hospital 1): S1 (4) = maxj {r1 (j) + S2 (4 − j)}

Optimal Allocation: Hospital 1: 2 doctors, Hospital 2: 0 doctors, Hospital 3: 2
doctors Maximum patients served: 13

rk
ica
e m
ad
ac

11 academicark
BCS503 - DAA Unit-4 AKTU

5 Backtracking
Definition
Backtracking is an algorithmic technique that systematically searches for solu-
tions by building candidates incrementally and abandoning a candidate (backtrack-
ing) as soon as it is determined that the candidate cannot lead to a valid solution.

5.1 General Framework

Algorithm
General Backtracking Algorithm:
1: procedure Backtrack(solution, level)
2: if solution is complete then
3: Process/Output solution
4: return
5: end if
6: for each candidate c at level do
7: if c is promising then
8: Add c to solution
9: Backtrack(solution, level + 1)
rk

10: Remove c from solution ▷ Backtrack

ica

11: end if
end for
m

12:
e

13: end procedure

ad
ac

5.2 Key Concepts

1. State Space Tree: Represents all possible solutions

2. Promising Node: Node that may lead to a solution

3. Non-promising Node: Node that cannot lead to a solution

4. Pruning: Eliminating non-promising branches

12 academicark
BCS503 - DAA Unit-4 AKTU

6 N-Queens Problem
6.1 Problem Statement
Definition
Place N queens on an N × N chessboard such that no two queens attack each
other. Queens attack along rows, columns, and diagonals.

6.2 Constraints
• No two queens in the same row

• No two queens in the same column

• No two queens in the same diagonal

6.3 Backtracking Solution

Algorithm
N-Queens Algorithm:
1: procedure NQueens(board[][], row, n)
rk

2: if row == n then
ica

3: Print board ▷ Solution found

4: return true
m

end if
e

5:
ad

6: for col ← 0 to n − 1 do
ac

7: if isSafe(board, row, col, n) then

8: board[row][col] ← 1 ▷ Place queen
9: if NQueens(board, row + 1, n) then
10: return true
11: end if
12: board[row][col] ← 0 ▷ Backtrack
13: end if
14: end for
15: return false
16: end procedure
17:
18: procedure isSafe(board[][], row, col, n)
19: for i ← 0 to row − 1 do
20: if board[i][col] == 1 then
21: return false ▷ Column check
22: end if
23: end for
24: for i, j ← row − 1, col − 1 down to 0, 0 do
25: if board[i][j] == 1 then
26: return false ▷ Left diagonal
27: end if

13 academicark
BCS503 - DAA Unit-4 AKTU

28: end for

29: for i, j ← row − 1, col + 1 down to 0, n − 1 do
30: if board[i][j] == 1 then
31: return false ▷ Right diagonal
32: end if
33: end for
34: return true
35: end procedure

rk
ica
e m
ad
ac

14 academicark
BCS503 - DAA Unit-4 AKTU

Example
Example: 4-Queens Problem
Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .

State Space Tree (Partial):

• Level 0 (Row 0): Try placing queen in columns 0, 1, 2, 3

• Level 1 (Row 1): For each valid placement in row 0, try columns in row 1

• Continue until all queens are placed or backtrack

Steps:

1. Place queen at (0, 1)

2. Try (1, 0): Attacked by (0, 1) - Skip

3. Try (1, 2): Attacked by (0, 1) - Skip

rk

4. Try (1, 3): Valid - Place queen

ica
m

5. Try (2, 0): Valid - Place queen

e
ad

6. Try (3, 2): Valid - Place queen

ac

7. Solution found!

6.4 Time Complexity

Important Note

• Worst Case: O(N !) - but pruning significantly reduces this

• Space Complexity: O(N 2 ) for board representation

15 academicark
BCS503 - DAA Unit-4 AKTU

7 Graph Coloring Problem

7.1 Problem Statement
Definition
Given a graph G = (V, E) and m colors, assign colors to vertices such that no two
adjacent vertices have the same color. The minimum number of colors needed is
called the chromatic number.

7.2 Backtracking Approach

Algorithm
Graph Coloring Algorithm:
1: procedure GraphColoring(graph[][], m, color[], v, V )
2: if v == V then
3: Print color ▷ All vertices colored
4: return true
5: end if
6: for c ← 1 to m do
7: if isSafe(graph, v, color, c, V ) then
color[v] ← c ▷ Assign color
rk

8:
9: if GraphColoring(graph, m, color, v + 1, V ) then
ica

10: return true

m

11: end if
e
ad

12: color[v] ← 0 ▷ Backtrack

end if
ac

13:
14: end for
15: return false
16: end procedure
17:
18: procedure isSafe(graph[][], v, color[], c, V )
19: for i ← 0 to V − 1 do
20: if graph[v][i] == 1 AND color[i] == c then
21: return false ▷ Adjacent vertex has same color
22: end if
23: end for
24: return true
25: end procedure

Example
Example: Graph Coloring with 3 Colors
Consider a graph with 4 vertices:
Adjacency Matrix:

16 academicark
BCS503 - DAA Unit-4 AKTU

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

Solution:

• Vertex 0: Color 1

• Vertex 1: Color 2

• Vertex 2: Color 3

• Vertex 3: Color 2

Chromatic number = 3

rk
ica
m
e
ad
ac

17 academicark
BCS503 - DAA Unit-4 AKTU

8 Hamiltonian Cycle Problem

8.1 Problem Statement
Definition
A Hamiltonian Cycle is a cycle in a graph that visits each vertex exactly once
and returns to the starting vertex. The problem is to determine whether such a
cycle exists in a given graph.

8.2 Backtracking Solution

Algorithm
Hamiltonian Cycle Algorithm:
1: procedure HamiltonianCycle(graph[][], path[], pos, V )
2: if pos == V then
3: if graph[path[pos − 1]][path[0]] == 1 then
4: return true ▷ Cycle found
5: else
6: return false
7: end if
rk

8: end if
for v ← 1 to V − 1 do
ica

9:
10: if isSafe(v, graph, path, pos) then
m

11: path[pos] ← v
e
ad

12: if HamiltonianCycle(graph, path, pos + 1, V ) then

ac

13: return true

14: end if
15: path[pos] ← −1 ▷ Backtrack
16: end if
17: end for
18: return false
19: end procedure
20:
21: procedure isSafe(v, graph[][], path[], pos)
22: if graph[path[pos − 1]][v] == 0 then
23: return false ▷ No edge
24: end if
25: for i ← 0 to pos − 1 do
26: if path[i] == v then
27: return false ▷ Already visited
28: end if
29: end for
30: return true
31: end procedure

18 academicark
BCS503 - DAA Unit-4 AKTU

Example
Example: Hamiltonian Cycle
Graph with 5 vertices:
Edges: (0,1), (1,2), (2,3), (3,4), (4,0), (0,2), (2,4)
Hamiltonian Cycle: 0 → 1 → 2 → 3 → 4 → 0
Path Construction:

1. Start at vertex 0

2. Visit 1 (adjacent to 0, not visited)

3. Visit 2 (adjacent to 1, not visited)

4. Visit 3 (adjacent to 2, not visited)

5. Visit 4 (adjacent to 3, not visited)

6. Check edge from 4 to 0: exists

7. Hamiltonian cycle found!

rk
ica
e m
ad
ac

19 academicark
BCS503 - DAA Unit-4 AKTU

9 Sum of Subsets Problem

9.1 Problem Statement
Definition
Given a set of positive integers S = {w1 , w2 , . . . , wn } and a target sum M , find all
subsets of S that sum to M .

9.2 Backtracking Solution

Algorithm
Sum of Subsets Algorithm:
1: procedure SumOfSubsets(w[], subset[], sum, remaining, i, n, M )
2: if sum == M then
3: Print subset ▷ Solution found
4: return
5: end if
6: if i == n OR sum + remaining < M OR sum > M then
7: return ▷ Not promising
8: end if
subset[i] ← w[i] ▷ Include w[i]
rk

9:
10: SumOfSubsets(w, subset, sum + w[i], remaining − w[i], i + 1, n, M )
ica

11: subset[i] ← 0 ▷ Exclude w[i]

m

12: SumOfSubsets(w, subset, sum, remaining − w[i], i + 1, n, M )

e
ad

13: end procedure

ac

9.3 Pruning Conditions

Important Note
Bounding Functions:

• Upper Bound: sum + remaining ≥ M

• Lower Bound: sum + w[i] ≤ M

If these conditions are violated, backtrack immediately.

Example
Example: Sum of Subsets
Given:

• Set: S = {3, 5, 6, 7, 8}

• Target sum: M = 15

Solutions:

20 academicark
BCS503 - DAA Unit-4 AKTU

• Subset 1: {3, 5, 7} → Sum = 15

• Subset 2: {7, 8} → Sum = 15

State Space Tree (Partial):

• Level 0: sum = 0, remaining = 29

• Level 1: Include 3 (sum=3) or Exclude 3 (sum=0)

• Level 2 (if 3 included): Include 5 (sum=8) or Exclude 5 (sum=3)

• Continue until sum = 15 or prune

rk
ica
em
ad
ac

21 academicark
BCS503 - DAA Unit-4 AKTU

10 Branch and Bound

Definition
Branch and Bound is an algorithmic paradigm for solving optimization problems
by systematically exploring the solution space, using bounds to eliminate branches
that cannot lead to optimal solutions.

10.1 Key Concepts

1. Branching: Dividing the problem into subproblems
2. Bounding: Computing upper/lower bounds for subproblems
3. Pruning: Eliminating subproblems based on bounds
4. Best-First Search: Exploring most promising nodes first

10.2 Differences from Backtracking

Backtracking Branch and Bound
Used for decision problems Used for optimization problems
DFS-based exploration Best-first or BFS exploration
Finds feasible solutions Finds optimal solutions
rk

Uses constraints for pruning Uses bounds for pruning

ica
m

10.3 General Framework

e
ad

Algorithm
ac

Branch and Bound Framework:

1: procedure BranchAndBound(problem)
2: Initialize priority queue Q with root node
3: bestSolution ← ∞ (for minimization)
4: while Q is not empty do
5: node ← extract node with best bound from Q
6: if node.bound ≥ bestSolution then
7: continue ▷ Prune this branch
8: end if
9: if node is a complete solution then
10: bestSolution ← node.value
11: else
12: Generate child nodes
13: for each child c do
14: Compute c.bound
15: if c.bound < bestSolution then
16: Add c to Q
17: end if
18: end for
19: end if

22 academicark
BCS503 - DAA Unit-4 AKTU

20: end while

21: return bestSolution
22: end procedure

rk
ica
me
ad
ac

23 academicark
BCS503 - DAA Unit-4 AKTU

11 Travelling Salesman Problem (TSP)

11.1 Problem Statement
Definition
Given a set of n cities and distances between every pair of cities, find the shortest
possible tour that visits each city exactly once and returns to the starting city.

11.2 Branch and Bound Approach

11.2.1 Cost Matrix Reduction
Row Reduction: Subtract minimum element of each row from all elements in that row.
Column Reduction: Subtract minimum element of each column from all elements
in that column.
Reduced Cost: Sum of all reduction values gives lower bound.

11.2.2 Bounding Function

Lower Bound = Reduced Cost + Cost of chosen edge

Algorithm
rk

TSP Branch and Bound Algorithm:

ica

1: procedure TSP BranchBound(costM atrix[][], n)

m

2: Reduce costM atrix and compute initial bound

e

Initialize priority queue with root node

ad

3:
4: minCost ← ∞
ac

5: while queue not empty do

6: node ← extract minimum bound node
7: if node.level == n − 1 then
8: Update minCost and optimal path
9: else
10: for each unvisited city i do
11: Create child node
12: Reduce cost matrix for child
13: Compute child bound
14: if child bound < minCost then
15: Add child to queue
16: end if
17: end for
18: end if
19: end while
20: return optimal path and minCost
21: end procedure

24 academicark
BCS503 - DAA Unit-4 AKTU

Example
Example: TSP using Branch and Bound
Cost Matrix:
A B C D
A ∞ 10 15 20
B 10 ∞ 35 25
C 15 35 ∞ 30
D 20 25 30 ∞

Step 1: Row Reduction

• Row A: Subtract 10 → Cost = 10

• Row B: Subtract 10 → Cost = 10

• Row C: Subtract 15 → Cost = 15

• Row D: Subtract 20 → Cost = 20

Total reduction = 55
Step 2: Column Reduction After row reduction, check columns. No further
reduction needed.
Step 3: Branching Start from A, explore edges A→B, A→C, A→D with their
rk

respective bounds.
ica

Optimal Tour: A → B → D → C → A with cost 80

e m
ad

11.3 Time Complexity

ac

Important Note

• Worst Case: O(n!)

• Average Case: Much better due to pruning

• Space Complexity: O(n2 )

11.4 Applications
• Vehicle routing

• Circuit board drilling

• DNA sequencing

• Network design

25 academicark
BCS503 - DAA Unit-4 AKTU

12 0/1 Knapsack using Branch and Bound

12.1 Bounding Functions
12.1.1 Upper Bound Calculation

Important Note

Upper Bound = Current profit + (Remaining capacity × best profit/weight ratio)

This provides an optimistic estimate using fractional knapsack relaxation.

Algorithm
Knapsack Branch and Bound:
1: procedure Knapsack BB(W, wt[], val[], n)
2: Sort items by value/weight ratio (descending)
3: Initialize queue with root node
4: maxP rof it ← 0
5: while queue not empty do
6: node ← extract maximum bound node
7: if node.bound > maxP rof it then
8: if node.level == n then
9: Update maxP rof it
rk

10: else
ica

11: Create left child (include item)

m

12: Create right child (exclude item)

e

13: Compute bounds for children

ad

14: if left child is feasible and promising then

ac

15: Add to queue

16: end if
17: if right child is promising then
18: Add to queue
19: end if
20: end if
21: end if
22: end while
23: return maxP rof it
24: end procedure

Example

Example: 0/1 Knapsack using Branch and Bound

Given:
• Items: {(w=2,v=40), (w=3,v=50), (w=5,v=100), (w=7,v=120)}
• Capacity: W = 10
Step 1: Sort by v/w ratio: {(w=2,v=40,r=20), (w=3,v=50,r=16.7),
(w=7,v=120,r=17.1), (w=5,v=100,r=20)}

26 academicark
BCS503 - DAA Unit-4 AKTU

Step 2: Build state space tree

• Root: level=0, profit=0, weight=0, bound=220

• Level 1: Include item 1 (w=2,v=40) or exclude

• Continue branching and pruning based on bounds

Optimal Solution: Items 1, 2, and 4 with total value = 190

rk
ica
m
e
ad
ac

27 academicark
BCS503 - DAA Unit-4 AKTU

13 Comparison: Backtracking vs Branch and Bound

13.1 Detailed Comparison

Aspect Backtracking Branch and Bound

Problem Type Feasibility/Decision problems Optimization problems
Goal Find any/all feasible solutions Find optimal solution
Search Strategy Depth-First Search (DFS) Best-First Search / BFS
Pruning Criteria Constraint violation Bound comparison
Data Structure Stack (implicit recursion) Priority Queue
Memory Usage Lower (O(depth)) Higher (stores all live nodes)
Solution Quality May not be optimal Guaranteed optimal
Examples N-Queens, Graph Coloring TSP, Knapsack
Bounding Function Not required Essential for pruning
Completeness Finds all solutions Finds one optimal solution

13.2 When to Use Which?

Important Note
Use Backtracking when:
rk

• Seeking feasible solutions

ica

• All solutions are needed

me

• Constraint satisfaction is primary concern

ad
ac

• Memory is limited

Use Branch and Bound when:

• Optimization is the goal

• Only best solution is needed

• Good bounding function is available

• More memory is available

28 academicark
BCS503 - DAA Unit-4 AKTU

14 Summary and Key Takeaways

14.1 Dynamic Programming
• Solves problems with overlapping subproblems and optimal substructure

• Two approaches: Memoization (top-down) and Tabulation (bottom-up)

• Examples: 0/1 Knapsack, Floyd-Warshall, Resource Allocation

• Time complexity often pseudo-polynomial

14.2 All Pairs Shortest Paths

• Floyd-Warshall: O(n3 ) for all pairs shortest paths

• Warshall’s Algorithm: Computes transitive closure

• Works with negative weights but not negative cycles

• Applications in network routing and graph analysis

14.3 Backtracking
• Systematic search with pruning of non-promising branches
rk
ica

• Used for constraint satisfaction problems

m

• Examples: N-Queens, Graph Coloring, Hamiltonian Cycle, Sum of Subsets

e
ad

• DFS-based exploration with explicit backtracking

ac

14.4 Branch and Bound

• Optimization technique using bounds to prune search space

• Best-first or breadth-first exploration

• Examples: TSP, 0/1 Knapsack optimization

• More memory intensive than backtracking but finds optimal solutions

14.5 Problem Selection Guidelines

Problem Characteristics Technique
Overlapping subproblems + optimal Dynamic Programming
substructure
All pairs analysis needed Floyd-Warshall / Warshall
Constraint satisfaction + feasibility Backtracking
Optimization + bound computation Branch and Bound
possible

29 academicark
BCS503 - DAA Unit-4 AKTU

15 Important Formulas and Complexities

15.1 Time Complexities Summary
Algorithm/Problem Time Complexity Space Complexity
0/1 Knapsack (DP) O(nW ) O(nW ) or O(W )
Floyd-Warshall O(n3 ) O(n2 )
Warshall’s Algorithm O(n3 ) O(n2 )
N-Queens (Backtracking) O(N !) worst O(N 2 )
Graph Coloring Exponential O(V )
Hamiltonian Cycle O(N !) worst O(N )
Sum of Subsets O(2n ) worst O(n)
TSP (Branch & Bound) O(n!) worst O(n2 )

15.2 Key Recurrence Relations

15.2.1 0/1 Knapsack
dp[i][w] = max(dp[i − 1][w], vi + dp[i − 1][w − wi ])

15.2.2 Floyd-Warshall
dist[i][j](k) = min(dist[i][j](k−1) , dist[i][k](k−1) + dist[k][j](k−1) )
rk
ica

15.2.3 Resource Allocation

m

Sk (x) = max {rk (j) + Sk+1 (x − j)}

e

j=0,1,...,x
ad
ac

30 academicark
BCS503 - DAA Unit-4 AKTU

16 Practice Problems
16.1 Problem 1: Modified Knapsack
A thief has a knapsack of capacity 15 kg. There are 4 items with the following weights
and values: (w=5,v=10), (w=4,v=40), (w=6,v=30), (w=3,v=50). Find the maximum
value the thief can carry using dynamic programming.

16.2 Problem 2: Floyd-Warshall

Given a graph with 5 vertices and weighted edges, apply Floyd-Warshall algorithm to
find shortest paths between all pairs. Consider negative edge weights.

16.3 Problem 3: N-Queens

Solve the 8-Queens problem and find at least two distinct solutions using backtracking.

16.4 Problem 4: TSP

Four cities A, B, C, D are given with distances. Find the shortest Hamiltonian cycle
using branch and bound technique.
rk

16.5 Problem 5: Graph Coloring

ica

Color a graph with 6 vertices using minimum colors. The graph represents a map where
m

adjacent regions must have different colors.

e
ad
ac

16.6 Problem 6: Sum of Subsets

Given set S = {5, 10, 12, 13, 15, 18} and target sum M = 30, find all possible subsets
using backtracking.

16.7 Problem 7: Resource Allocation

Allocate 10 units of budget among 4 projects where each project has different return
functions. Maximize total return using dynamic programming.

31 academicark
BCS503 - DAA Unit-4 AKTU

17 Exam Tips and Important Points

Important Note
For AKTU Exams:

1. Understand Concepts: Focus on when to apply each technique

2. Practice Algorithms: Write pseudocode from memory

3. Time/Space Complexity: Always mention complexity analysis

4. State Space Trees: Draw partial trees for backtracking problems

5. DP Tables: Show step-by-step table filling for DP problems

6. Examples: Work through at least 2-3 examples per topic

7. Comparisons: Be ready to compare different techniques

8. Applications: Know real-world applications of each algorithm

17.1 Common Mistakes to Avoid

rk

1. Confusing backtracking with branch and bound

ica

2. Incorrect base cases in recursive formulations

e m

3. Not considering boundary conditions in DP

ad
ac

4. Forgetting to backtrack (removing elements from solution)

5. Incorrect bound computation in branch and bound

6. Not optimizing space in DP when possible

7. Missing pruning conditions in backtracking

17.2 Quick Revision Checklist

□ Dynamic Programming principles and approaches

□ 0/1 Knapsack - both DP table and space-optimized

□ Floyd-Warshall complete algorithm

□ Warshall’s algorithm for transitive closure

□ Resource allocation DP formulation

□ Backtracking general framework

□ N-Queens complete solution

□ Graph Coloring algorithm

32 academicark
BCS503 - DAA Unit-4 AKTU

□ Hamiltonian Cycle detection

□ Sum of Subsets with pruning

□ Branch and Bound framework

□ TSP using Branch and Bound

□ Differences: Backtracking vs Branch and Bound

rk
ica
em
ad
ac

33 academicark
BCS503 - DAA Unit-4 AKTU

All the Best for Your Exams!

Visit AcademicArk for more study materials

https://academicark-mvp8.onrender.com/

Quality notes for AKTU students

rk
ica
m
e
ad
ac

34 academicark