Design and Analysis of Algorithms

E1ITB303 – Exam Notes: Modules 4 & 5

All 7 Questions – Complete PPT-Based Answers

1. Graph Coloring Problem using Backtracking

Definition
Graph coloring refers to the problem of coloring vertices of a graph such that no two adjacent vertices
have the same color. This is also called the vertex coloring problem. If coloring is done using at most m
colors, it is called m-coloring.

Chromatic Number
The minimum number of colors needed to color a graph is called its chromatic number. For example, a
simple path graph can be colored with a minimum of 2 colors.

Backtracking Approach
• Assign colors to vertices one by one.
• For each vertex, try all possible colors.
• Use a function isSafe() to check whether the current color conflicts with adjacent vertices.
• If valid → proceed to the next vertex.
• If conflict → backtrack (try next color or go back to previous vertex).

Constraint Handling
• Main constraint: adjacent vertices must NOT share the same color.
• Before assigning a color, check all adjacent vertices.
• If a conflict occurs, that branch is pruned (cut off).

Reduction of Search Space

• Without constraints → total possibilities = mⁿ
• With constraints → invalid color combinations are eliminated early.
• This avoids exploring unnecessary branches and improves efficiency.

Example from PPT

Graph: Vertices = {V1, V2, V3}, Edges = {(V1,V2), (V2,V3)}, Colors = {Red, Green}

Step Action
1 Assign color to V1 → Red
2 Move to V2 → Red conflicts with V1 ❌ → Try Green ✅
3 Move to V3 → Green conflicts with V2 ❌ → Try Red ✅
Done V1=Red, V2=Green, V3=Red ✅ Valid Solution
Other valid solution: V1=Green, V2=Red, V3=Green ✅

Conclusion
Backtracking with constraints efficiently solves the graph coloring problem by pruning invalid solutions
early, thereby reducing the search space from mⁿ to a much smaller number of actual valid
explorations.
2. All-Pairs Shortest Path using Floyd's Algorithm

Definition
Floyd's Algorithm finds the shortest distance between EVERY pair of vertices in a weighted directed
graph. It uses Dynamic Programming by considering each vertex as an intermediate vertex one at a
time.

Key Formula
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )
Where k is the current intermediate vertex being considered.

Algorithm Steps
• Initialize the distance matrix with direct edge costs (∞ if no edge).
• Set dist[i][i] = 0 for all vertices.
• For each intermediate vertex k (from 1 to n):
– For each pair (i, j), check if going through k gives a shorter path.
– If dist[i][k] + dist[k][j] < dist[i][j], update dist[i][j].
• After all iterations, dist[i][j] holds the shortest path from i to j.

Step-by-Step Example (from Lab PPT)

Initial Cost Matrix (4 cities: A, B, C, D):

A B C D

A 0 3 ∞ 7
B 8 0 2 ∞
C 5 ∞ 0 1
D 2 ∞ ∞ 0

k = 0 (A as intermediate):
• B→D via A: B→A + A→D = 8 + 7 = 15 < ∞ → update B→D = 15
• C→B via A: C→A + A→B = 5 + 3 = 8 < ∞ → update C→B = 8

A B C D

A 0 3 ∞ 7
B 8 0 2 15
C 5 8 0 1
D 2 5 ∞ 0

k = 1 (B as intermediate):
 • A→C via B: A→B + B→C = 3 + 2 = 5 < ∞ → update A→C = 5
• D→C via B: D→B + B→C = 5 + 2 = 7 < ∞ → update D→C = 7

A B C D

A 0 3 5 7
B 8 0 2 15
C 5 8 0 1
D 2 5 7 0

k = 2 (C as intermediate):
• A→D via C: A→C + C→D = 5 + 1 = 6 < 7 → update A→D = 6
• B→D via C: B→C + C→D = 2 + 1 = 3 < 15 → update B→D = 3

A B C D

A 0 3 5 6
B 7 0 2 3
C 5 8 0 1
D 2 5 7 0

k = 3 (D as intermediate):
No further improvements. Final matrix remains the same.

A B C D

A 0 3 5 6
B 7 0 2 3
C 5 8 0 1
D 2 5 7 0

This final matrix gives the shortest distance between every pair of vertices.

Time Complexity
O(n³) — Three nested loops over n vertices
3. N-Queens Problem using Backtracking

Problem Statement
Place N queens on an N×N chessboard such that no two queens attack each other.

Queen Movement Rules

• Each queen can move horizontally, vertically, or diagonally.
• Therefore, no two queens can be in the same row, column, or diagonal.

Constraints
• One queen per row
• One queen per column
• No diagonal conflicts

Solution Count
• N = 4 → 2 solutions
• N = 8 → 92 solutions

Backtracking Approach
• Place queens row by row.
• For each row, try all columns.
• If safe → place queen and move to next row.
• If not safe → skip this column.
• If stuck (no column works) → backtrack to previous row.

Safety Check Conditions — While placing queen at (row, col):

• No queen in the same column
• No queen in left diagonal → check (row − col) is unique
• No queen in right diagonal → check (row + col) is unique

Key Concept (from PPT)

The main challenge is to place queens such that no two queens attack each other. Backtracking is
commonly used: it tries positions row by row and backtracks whenever a conflict occurs.

Example: 4-Queens Solution

Row Column Chosen Reason

1 Col 2 Safe – no conflicts
2 Col 4 Safe – not same col, not same diagonal
3 Col 1 Safe – passes all checks
4 Col 3 Safe – completes one valid arrangement
Valid arrangement: Q at (1,2), (2,4), (3,1), (4,3) ✅
4. Hamiltonian Cycle Problem using Backtracking

Definition
A Hamiltonian Cycle is a cycle in a graph that:
• Visits each vertex exactly once
• Returns to the starting vertex
If such a cycle exists, the graph is called a Hamiltonian Graph.

Key Concepts
• Hamiltonian Path: visits every vertex exactly once; does NOT need to return to start.
• Hamiltonian Cycle: a Hamiltonian path that forms a cycle (start = end).

Properties
• A graph may have one, multiple, or NO Hamiltonian cycle.
• There is no simple formula to determine if a graph is Hamiltonian.

Backtracking Approach — Algorithm Steps

• Start from any vertex.
• Add it to the path.
• Try adding adjacent vertices one by one.
• Ensure the vertex is not already visited.
• If all vertices are visited AND the last vertex has an edge back to the first → Cycle found!
• If stuck → backtrack and try another adjacent vertex.

Step-by-Step Example (from PPT — 4 vertices: 0,1,2,3)

Step Action Current Path

1 Start from vertex 0 [0 _ _ _]
2 From 0 → choose 1 (adjacent) [0 1 _ _]
3 From 1 → 0 already visited; choose [0 1 2 _]
2
4 From 2 → 0,1 visited; choose 3 [0 1 2 3]
5 Check: edge from 3 → 0? ✅ YES → 0→1→2→3→0 ✅
Cycle found!

Final Hamiltonian Cycle: 0 → 1 → 2 → 3 → 0 ✅

📝 If at any step, no adjacent unvisited vertex exists, the algorithm backtracks to the previous step and tries
the next option.
5. Subset Sum Problem using Backtracking

Problem Definition
Given a set of n positive integers and a target value S, find all subsets whose sum equals S.

Example 1 (from PPT)

Set: {5, 10, 12, 13, 15, 18} Target: 30
Valid subsets:
• {5, 10, 15} → 5+10+15 = 30 ✅
• {12, 18} → 12+18 = 30 ✅

Backtracking Idea
At each step, for every element decide:
• Include the element in the current subset (Left branch = 1)
• Exclude the element from the current subset (Right branch = 0)
• Explore all combinations using the State Space Tree
• Prune (stop early) if:
– Current sum exceeds target
– No possibility of reaching the target with remaining elements

Example 2 (from PPT — State Space Tree)

Set = {5, 10, 12, 13} Target = 22
State Space Tree: Each node shows (current sum). Left branch = Include (1), Right branch = Exclude
(0).

Decision Path Running Sum Result

Include 5, Include 10, 5+10+12 = 27 27 > 22 → Prune ❌
Include 12
Include 5, Include 10, 5+10+13 = 28 28 > 22 → Prune ❌
Exclude 12, Include 13
Include 5, Exclude 10, 5+12 = 17 17 < 22, no more elements → Dead end ❌
Include 12, Exclude 13
Include 5, Exclude 10, 5+13 = 18 → +? Can't reach 22 → Prune ❌
Exclude 12, Include 13
Exclude 5, Include 10, 10+12 = 22 22 = Target ✅ FOUND!
Include 12, Exclude 13

Valid subset found: {10, 12} → 10+12 = 22 ✅

6. Travelling Salesperson Problem (TSP) using Branch and
Bound

Problem Statement
Given n cities and distances between every pair, find the shortest possible tour that:
• Visits each city exactly once
• Returns to the starting city
Example: Cities A, B, C, D → Find minimum cost cycle like A → B → C → D → A

Branch and Bound — Key Concepts

• Branch: Divide the problem into smaller subproblems. Represented as a state-space tree. Each
node = partial solution.
• Bound: Calculate a lower bound (minimum possible cost) for each node. Estimate best possible
solution from that node.
• Pruning: If a node cannot give a better solution than current best → discard it. Saves time and
avoids unnecessary computation.

Terminology
• State-space tree → Tree of all possible solutions
• Live node → Node still to be explored
• Dead node → Node discarded (pruned)
• E-node (Expansion node) → Currently explored node

Bounding Function (Very Important!)

Lower Bound (LB) = Cost so far + Row reduction + Column reduction
OR: LB = Sum of minimum edges required to complete the tour
If a node's bound ≥ current best solution → prune it (discard it).

Algorithm Steps

Step Action
Step 1 Represent the problem as a cost matrix of distances between cities.
Step 2 Compute Initial Lower Bound (Root): Row reduction + Column reduction.
Step 3 Start from root city. Generate child nodes by visiting unvisited cities.
(Branch)
Step 4 For each partial path: Current path cost + Estimated remaining cost (LB).
Step 5 Select node with minimum bound (using priority queue).
Step 6 If node's bound ≥ current best → discard. Else → expand.
(Prune)
Step 7 Continue branching + bounding until all nodes explored or pruned.
Step 8 Path with minimum cost = optimal tour.
Complete Step-by-Step Example (from PPT — 4 cities: A, B, C, D)
Step 1 — Initial Cost Matrix:
(∞ means no direct road; diagonal = 0)

Step 2 — Row Reduction:

Find minimum in each row and subtract from that row:
• Row A → min = 10 (subtract 10 from all entries in row A)
• Row B → min = 4
• Row C → min = 2
• Row D → min = 6
Row reduction cost = 10 + 4 + 2 + 6 = 22

Step 3 — Column Reduction:

Find minimum in each column of the row-reduced matrix and subtract:
• Col A → min = 1
• Col B → min = 0
• Col C → min = 12
• Col D → min = 0
Column reduction cost = 1 + 0 + 12 + 0 = 13

Step 4 — Initial Lower Bound:

Total LB = Row Reduction + Column Reduction = 22 + 13 = 35

Step 5 — Branching from A:

Possible paths from A: A→B, A→C, A→D
Evaluate and expand the least-cost branch.

Step 6 — Optimal Path (after complete branching & pruning):

Edge Cost
A→D 10
D→B 6
B→C 16
C→A 3
Total 35

✅ Optimal Tour: A → D → B → C → A Minimum Cost = 35

7. Multistage Graph Problem using Dynamic Programming

Definition
A Multistage Graph G = (V, E) is a directed acyclic graph (DAG) where vertices are partitioned into k
disjoint subsets (stages) S = {s1, s2, ..., sk} such that edges go only from stage i to stage i+1.
• Source = vertex in s1 (stage 1)
• Sink = vertex in sk (last stage)
• |s1| = |sk| = 1 → single source and single destination
• cost(i,j) = cost of edge from vertex i to j

Problem
Find the path with minimum cost from source s to sink t.

Algorithm — Backward Dynamic Programming Approach

The cost is computed backward from the last stage to the first.
Cost(i, j) = min over all k { c(j, k) + Cost(i+1, k) }

Input / Output
• Input: n → number of vertices, cost[i][j] → edge costs, k → number of stages
• Output: Minimum cost from source to destination + Optimal path

Step-by-Step Example (from PPT — 9 nodes, 5 stages)

Stages: 1={1}, 2={2,3}, 3={4,5,6}, 4={7,8}, 5={9}

Step 1 — Cost(K−2, j) → Stage 3 nodes: 4, 5, 6

• Cost(3,4) = min{ c(4,7)+Cost(7,9), c(4,8)+Cost(8,9) } = 7 → Best: 4→8→9
• Cost(3,5) = min{ c(5,7)+Cost(7,9), c(5,8)+Cost(8,9) } = 5 → Best: 5→8→9
• Cost(3,6) = min{ c(6,7)+Cost(7,9), c(6,8)+Cost(8,9) } = 5 → Best: 6→8→9

Step 2 — Cost(K−3, j) → Stage 2 nodes: 2, 3

• Cost(2,2) = min{ c(2,4)+Cost(3,4), c(2,6)+Cost(3,6) }
– = min{ c(2,4)+7, c(2,6)+5 } = 8 → Best: 2→6→8→9
• Cost(2,3) = min{ c(3,4)+Cost(3,4), c(3,5)+Cost(3,5), c(3,6)+Cost(3,6) }
– = min{ ... } = 10 → Best: 3→5→8→9

Step 3 — Cost(K−4, j) → Stage 1 node: 1 (Source)

• Cost(1,1) = min{ c(1,2)+Cost(2,2), c(1,3)+Cost(2,3) }
– = min{ c(1,2)+8, c(1,3)+10 }
– = min{ ?+8, ?+10 } → Minimum value = 12

Final Answer
✅ Minimum Cost Path: 1 → 3 → 5 → 8 → 9 Total Cost = 12
Algorithm Summary Table

Stage Nodes Cost Computed

Stage 5 (Sink) {9} Cost = 0 (destination)
Stage 4 {7, 8} Cost(7,9), Cost(8,9)
Stage 3 {4, 5, 6} Cost(3,4)=7, Cost(3,5)=5, Cost(3,6)=5
Stage 2 {2, 3} Cost(2,2)=8, Cost(2,3)=10
Stage 1 (Source) {1} Cost(1,1)=12 → Minimum = 12

Quick Revision Summary

Topic Technique Key Formula / Rule Result

Graph Coloring Backtracking isSafe() — no adjacent same Prune invalid
color colors early
Floyd's Algorithm Dynamic dist[i][j] = min(dist[i][j], dist[i][k] All-pairs shortest
Programming +dist[k][j]) path — O(n³)
N-Queens Backtracking Check col, left-diag (r-c), right- Row-by-row
diag (r+c) placement
Hamiltonian Cycle Backtracking Visit all once + return to start 0→1→2→3→0
Subset Sum Backtracking Include/Exclude; Prune if sum > Find all subsets
target = target
TSP Branch & Bound LB = row reduce + col reduce; Optimal Tour,
prune if LB ≥ best Min Cost
Multistage Graph Dynamic Cost(i,j) = min{c(j,k) + Backward DP,
Programming Cost(i+1,k)} min cost path

— All the best for your exam! —