Unit – V ALGORITHM DESIGN TECHNIQUES

Part A
1. Define Backtracking.
Backtracking is a problem-solving technique that builds a solution step-by-step and removes
(“backtracks”) those steps when they lead to a dead-end. It systematically searches all
possible configurations until a valid solution is found.

2. What is the goal of the N-Queen problem?

The goal of the N-Queen problem is to place N queens on an N×N chessboard such that no
two queens attack each other; meaning no two queens share the same row, column, or
diagonal.

3. Explain how backtracking is used in solving the N-Queen problem.

In N-Queen, queens are placed row by row. After placing a queen in a valid position:
• Move to the next row
• If no safe position exists, remove the previous queen (backtrack)
• Continue until all queens are safely placed
Thus, it eliminates invalid board configurations early.

4. Why is backtracking considered a depth-first search technique?

Backtracking explores one complete path or decision sequence deeply before moving to
another option. It goes down a path fully (DFS style) and backtracks only when the path fails.

5. List two problems solved using backtracking.

• N-Queen problem
• Sudoku solving
(Other examples: Graph coloring, Maze traversal)

6. Define Branch and Bound.

Branch and Bound is a state-space search method for optimization problems. It divides the
problem into smaller subproblems (branch) and uses bounds to eliminate subproblems that
cannot lead to an optimal solution.
7. What type of problem is Travelling Salesman Problem (TSP)?
TSP is a combinatorial optimization problem. The goal is to find the minimum cost path that
visits all cities exactly once and returns to the starting city.

8. How does bounding help in Branch and Bound method?

Bounding calculates a lower or upper cost estimate for each partial solution. If this bound is
worse than the current best solution, the branch is discarded, reducing unnecessary
exploration.

9. Why is Branch and Bound suitable for TSP?

Because TSP requires finding the optimal (minimum cost) route among many possibilities.
Branch and Bound effectively prunes non-optimal paths using bounds, reducing computation
drastically.

10. Mention two key components of the Branch and Bound algorithm.
• Branching: Generating new subproblems from the current node
• Bounding: Calculating bounds to check if the subproblem is promising

11. What is the principle of optimality in Dynamic Programming?

This principle states:
“An optimal solution to a problem contains optimal solutions to its subproblems.”
DP relies on solving smaller overlapping subproblems to build the best final solution.

12. Difference betwen 0/1 Knapsack and Fractional Knapsack.

Feature 0/1 Knapsack Fractional Knapsack

Item selection Entire item taken or not Items can be split into fractions
Method used Dynamic Programming Greedy Strategy
Complexity Higher Lower

13. How does Dynamic Programming solve the 0/1 Knapsack problem?
DP builds a table considering each item and each capacity.
It chooses the maximum value either by:
• Including the item (if weight allows), or
• Excluding it
The best value at each step is stored and reused, avoiding repeated computation.
14. Why is Dynamic Programming preferred over recursion for knapsack problems?
DP avoids repeated computation of the same subproblems.
This reduces time complexity from exponential to polynomial and makes the algorithm more
efficient and practical.

15. What strategy does the greedy method follow in Fractional Knapsack?
Greedy chooses items based on the highest value-to-weight ratio first.
It keeps adding the most profitable items until the knapsack is full, even if the last item is
taken only fractionally.

Part B

[Link] the backtracking technique to solve the 4-Queen problem. Draw the state space
tree and explain each step in placing the queens.

1. Brief definition and approach

Backtracking is a systematic search technique that builds candidates for the solution
incrementally and abandons a candidate as soon as it determines that the candidate cannot
possibly be completed to a valid solution.

For the N-Queen problem we place queens row by row. At each row we try columns one by
one, check if placing a queen is safe, go deeper if safe, and backtrack if no column is safe.

2. Pseudocode

solveNQueens(row):
if row > N:
output solution
return
for col from 1 to N:
if isSafe(row, col):
placeQueen(row, col)
solveNQueens(row + 1)
removeQueen(row, col) # backtrack

isSafe(r, c):
for each previous row i from 1 to r-1:
if queen at (i, c) or |i - r| == |col(i) - c|:
 return False
return True
[Link] Programming: Principles and Comparison
with Divide & Conquer
Dynamic Programming (DP) is an optimization technique used to solve complex problems by
breaking them down into simpler overlapping subproblems. It is highly effective for
problems that exhibit optimal substructure and overlapping subproblems.

✅ Principles of Dynamic Programming Optimal Substructure

A problem has optimal substructure if an optimal solution can be constructed from

optimal solutions of its subproblems.
Example
Shortest path from A to C through B is optimal only if A→B and B→C are
individually optimal.

1. Overlapping Subproblems

Subproblems recur multiple times.

Example
Fibonacci numbers: F(5) requires F(4), F(3); F(4) again needs F(3), F(2).

2. Memoization or Tabulation

DP avoids repeated work by storing results:

o Top-Down DP (Memoization)
Recursive with caching of computed results.
o Bottom-Up DP (Tabulation)
Iteratively builds solutions from base cases upward.
3. State and State Transition

DP defines:

o A state representing a subproblem

o A transition that relates a state to previous computed states
Example (Knapsack):
dp[i][w] = max(dp[i-1][w], profit[i] + dp[i-1][w-weight[i]])
4. Optimality Verification

DP ensures final selected result is optimal by comparing multiple candidate choices.

Applications of Dynamic Programming

Shortest path problems (e.g., Floyd-Warshall, Bellman-Ford)
  Matrix chain multiplication
 Knapsack problem
 Longest Common Subsequence (LCS)
 Coin change problem

[Link] the differences between 0/1 Knapsack and Fractional Knapsack. For a
knapsack of capacity 50 and the following items:
Item Profit Weight
1 60 10
2 100 20
3 120 30
Explain which technique (DP or Greedy) is suitable and why.

Feature 0/1 Knapsack Fractional Knapsack

Item cannot be divided. Either take entire Items can be broken into
Item selection
item (1) or leave it (0) fractions

Cannot directly choose based on Greedy selection based on

Strategy
profit/weight ratio highest P/W ratio

Greedy usually fails. Needs Dynamic Greedy always yields optimal

Optimal Solution
Programming or Backtracking solution

Greedy: O(n log n) or O(n)

Complexity DP: O(nW) (pseudo-polynomial)
after sorting

Discrete/indivisible items like exam Continuous/divisible material

Suitable for
slots, laptops like gold, fuel

Guarantees optimal due to

Accuracy Guarantees optimal using DP greedy property

Knapsack
Capacity:50

Profit
Item Weight (W) P/W
(P)

1 60 10 6.0

2 100 20 5.0
Feature 0/1 Knapsack Fractional Knapsack

3 120 30 4.0
Sorted by P/W ratio (descending):
Item1 → Item2 → Item3

Greedy Approach: Fractional Knapsack

Step-by-step filling:

1️⃣Add Item1 completely

Weight left = 50 − 10 = 40
Profit = 60

2️⃣ Add Item2 completely

Weight left = 40 − 20 = 20
Profit = 60 + 100 = 160

3️⃣ Only 20 of Item3 fits (20/30 = 2/3)

Profit = 160 + (2/3 × 120)
Profit = 160 + 80 = 240

✅Fractional Knapsack Result

 Max Profit = 240

 Technique used: Greedy
 0/1 Knapsack (DP Approach)
 Try different combinations:

Selected Items Total Weight Total Profit

1+2 30 160
1+3 40 180
2+3 50 220

[Link] how Dynamic Programming improves efficiency in solving the 0/1 Knapsack
problem for the following:

Compare the time complexity with recursion.

Dynamic Programming (DP) is a powerful technique for solving optimization problems like
the 0/1 Knapsack problem. Let's dive deep into how DP improves efficiency and apply it to
your specific example with a detailed explanation and tabular solution.
Knapsack Capacity W = 30
Understanding the 0/1 Knapsack Problem
The 0/1 Knapsack problem asks: Given a set of items, each with a weight and a profit, and a
knapsack with a maximum weight capacity, determine the maximum profit you can achieve
by selecting items such that:
 You either take an item (1) or leave it (0).
 The total weight does not exceed the knapsack's capacity.
📊 Given Data
Item Weight (W) Profit (P)

1 18 54

2 19 38

3 15 60
Knapsack Capacity (C) = 30

DP Table Construction
We create a 2D table dp[i][w] where:

 i = item index (0 to n)
 w = weight capacity (0 to C)

Each cell dp[i][w] stores the maximum profit using the first i items and capacity w.

Initialization:

 dp[0][w] = 0 for all w (no items → no profit)

Transition Formula:

If item ihas weight w iand profit pi:

 If w i> w : dp[i][w] = dp[i-1][w] (can't include item)

 Else: dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_i] + p_i)
 Step-by-Step Table (Simplified for Capacity 0–30)

Here’s a condensed version of the DP table showing only relevant capacities:

Item 1 (W=18, Item 2 (W=19, Item 3 (W=15, Max

Capacity
P=54) P=38) P=60) Profit
0–14 0 0 0 0
15–17 0 0 60 60
18 54 0 60 60
19–29 54 60 60 60
30 54 60 60 60

Now we check combinations:

 Item 1 + Item 3 = 18 + 15 = 33 → exceeds capacity

 Item 2 + Item 3 = 19 + 15 = 34 → exceeds capacity
 Item 1 + Item 2 = 18 + 19 = 37 → exceeds capacity

So, only one item can be selected. The best is Item 3 with profit 60.

 Maximum Profit: 60
 Selected Item: Item 3 (Weight = 15, Profit = 60)

[Link] the Greedy method to solve the Fractional Knapsack problem: CO5 K3 W=6,
Given Data

Show step-by-step selection based on profit/weight ratio.

Item Weight Profit

1 18 54

2 19 38

3 15 60
Knapsack capacity W =6
Step 1: Calculate Profit/Weight Ratio
 Profit
We compute the ratio for each item:
Weight
Item Profit/Weight Ratio
54
1 =3.0
18
38
2 =2.0
19
60
3 =4.0
15
📊 Step 2: Sort Items by Ratio (Descending)
Sorted order based on ratio: Item 3 → Item 1 → Item 2
🧮 Step 3: Greedy Selection
Start filling the knapsack with the highest ratio item first:
✅ Item 3:
 Weight = 15, but knapsack capacity = 6 → take fraction
6
 Fraction taken = =0.4
15
 Profit gained = 0.4 × 60=24
 Knapsack is now full
🧾 Final Answer
 Total weight used: 6
 Total profit: 24
 Item selected: 40% of Item 3

6. Evaluate why Greedy method fails for 0/1 Knapsack problem using the following
items:Capacity = 50, Items = (Profit, Weight): (60,10), 100,20), (120,30),Compare the
Greedy result with the DP result.

 Knapsack Capacity: 50
 Items:

Item Profit Weight Profit/Weight Ratio

1 60 10 6.0
2 100 20 5.0
Item Profit Weight Profit/Weight Ratio
3 120 30 4.0

Greedy Method (Based on Profit/Weight Ratio)

The Greedy method chooses items with the highest profit-to-weight ratio first, aiming
for quick gains.

Steps:

1. Sort items by Profit/Weight ratio: Item 1 (6.0), Item 2 (5.0), Item 3 (4.0)
2. Start adding items until capacity is full:
o Add Item 1 → Weight = 10, Profit = 60
o Add Item 2 → Weight = 30, Profit = 100
o Total Weight = 10 + 20 = 30 (still under 50)
o Add Item 3 → Weight = 30 → Exceeds capacity (30 + 30 = 60 > 50) → ❌
Cannot add

✅ Greedy Result:

 Items Taken: Item 1 and Item 2

 Total Weight: 30
 Total Profit: 160

🧠 Dynamic Programming Method

DP explores all combinations of items and chooses the one with maximum profit
without exceeding capacity.

DP Table Setup:

We build a table dp[i][w] where:

 i = item index (0 to 3)
 w = weight capacity (0 to 50)

Key Combinations:

 Item 2 + Item 3 → Weight = 20 + 30 = 50 ✅

 Profit = 100 + 120 = 220 ✅
 This combination is not considered by Greedy, because it skips Item 1 (which has
highest ratio)

✅ DP Result:

 Items Taken: Item 2 and Item 3

 Total Weight: 50
 Total Profit: 220
 🔍 Comparison Summary

Method Items Selected Total Weight Total Profit Optimal?

Greedy Item 1, Item 2 30 160 ❌ No
Dynamic Prog Item 2, Item 3 50 220 ✅ Yes

❌ Why Greedy Fails in 0/1 Knapsack

 Greedy assumes local optimal choices lead to global optimum — not true for 0/1
Knapsack.
 It cannot split items (unlike fractional knapsack), so skipping a high-ratio item may
lead to better overall profit.
 It misses combinations that yield higher profit due to rigid selection order.

✅ Why DP Succeeds

 DP considers all combinations and remembers subproblem results.

 It guarantees the optimal solution by exploring every possibility within constraints.

[Link] how the Backtracking algorithm solves the 4-Queens problem. Illustrate the
recursive function with decision points and show how backtracking eliminates invalid
solutions.

The Backtracking algorithm solves the 4-Queens problem by placing queens row by row,
recursively checking for safe positions, and backtracking when conflicts arise. It explores all
valid configurations until a solution is found.

Problem Overview:

4-Queens

Place 4 queens on a 4×4 chessboard such that:

 No two queens share the same row, column, or diagonal.

🔁 Backtracking Strategy

1. Start from row 0 and try placing a queen in each column.

2. Check if the position is safe (no queen in same column or diagonal).
3. If safe, place the queen and move to the next row.
4. If no valid position in a row, backtrack to the previous row and try a different column.
5. Repeat until all 4 queens are placed or all possibilities are exhausted.

Decision Points and Elimination

Let’s walk through the recursive decision tree:

 Row 0

 Try placing queen at (0,0), (0,1), (0,2), (0,3)

Suppose we place at (0,1)

Row 1

 Check columns: (1,0), (1,1), (1,2), (1,3)

 (1,1) is invalid (same column), (1,0) and (1,2) are invalid (diagonal)
 Place at (1,3)

Row 2

 Try columns: (2,0), (2,1), (2,2), (2,3)

 Only (2,0) is safe

Row 3

 Try columns: (3,0), (3,1), (3,2), (3,3)

 Only (3,2) is safe

🎉 Valid configuration found:

Code

0100

0001

1000

0010

If any row has no safe column, the algorithm backtracks to the previous row and tries a
different column.

🔍 How Backtracking Eliminates Invalid Solutions

 Conflict detection: Before placing a queen, is_safe() checks for column and diagonal
threats.
 Undoing choices: If a dead-end is reached, the algorithm removes the last queen and
tries the next possibility.
 Exhaustive search: All paths are explored, but invalid ones are pruned early.

8. Analyze the process of solving the Travelling Salesperson Problem (TSP) using the
Branch and Bound [Link] how the cost matrix is used, how lower bounds are
calculated, and how unnecessary paths are eliminated during the search for the optimal
solution.
The Branch and Bound method solves the Travelling Salesperson Problem (TSP) by
systematically exploring paths using a cost matrix, calculating lower bounds to estimate
minimum tour costs, and pruning paths that cannot yield better solutions than the current best.

Step 1: Constructing the Cost Matrix

 The cost matrix is a 2D array where each cell C [i][ j]represents the cost of traveling
from city ito city j .
 Diagonal entries C [i][i]are set to ∞ (or a very large number) to prevent revisiting the
same city.

Example:

A B C D
A ∞ 10 15 20
B 10 ∞ 35 25
C 15 35 ∞ 30
D 20 25 30 ∞

Step 2: Calculating Lower Bounds

To estimate the minimum cost from a node (partial tour), we calculate a lower bound using
matrix reduction:

1. Row Reduction: Subtract the minimum value in each row from all entries in that row.
2. Column Reduction: Do the same for columns.
3. Lower Bound = Sum of all row and column minimums.

This gives a baseline cost for completing the tour from that node.

Step 3: Branching

 From the current node (partial path), generate child nodes by choosing the next city to
visit.
 For each child, update the cost matrix:
o Set the row of the current city and column of the next city to ∞.
o Set the reverse path (next → current) to ∞ to prevent cycles.
 Recalculate the lower bound for each child node.
 Step 4: Bounding and Pruning
 Maintain a global variable for the best cost found so far.
 If a child node’s lower bound exceeds this cost, prune it (discard the path).
 Continue exploring only promising nodes with lower bounds less than the current
best.

Step 5: Termination

 The algorithm terminates when all nodes are either explored or pruned.
 The path with the lowest cost among complete tours is the optimal solution.
 Part C
[Link] the following instance of the 0/1, knapsack problem given the knapsack capacity
in W=10 using dynamic programming and explain it. Item Profit Weight.

Knapsack Capacity W =10

Dynamic Programming Approach

We create a 2D table dp[i][w] where:

 i = item index (from 0 to 4)

 w = weight capacity (from 0 to 10)
 dp[i][w] stores the maximum profit using first i items and capacity w

Step-by-Step Table Construction

1. Initialization:
o For i=0 (no items), all dp[0][w] = 0
o For w=0 (zero capacity), all dp[i][0] = 0
2. Recursive Relation: For each item iand capacity w :
o If item’s weight ≤ w :

dp [i][w]=max ⁡(dp[i−1][w ], dp [i−1][w−weighti ]+ profit i )

 Else:

dp [i][w]=dp[i−1][w ]
Final DP Table Snapshot (Simplified)
Capacity
0 1 2 3 4 5 6 7 8 9
→
Item 1 0 0 0 0 0 10 10 10 10 10
Item 2 0 0 0 0 40 40 40 40 50 50
Item 3 0 0 0 0 40 40 40 40 50 70
Item 4 0 0 0 50 50 50 50 90 90 90

Final Result
 Maximum Profit: ₹90

 Items Selected: Item 2 (₹40, 4kg) + Item 4 (₹50, 3kg) → Total weight = 7kg

3. Evaluate the performance of Branch and Bound in solving the Travelling

Salesman Problem (TSP) for the following cost matrix:

Show the bounding process and pruning decisions.

Branch and Bound solves the Travelling Salesman Problem (TSP) efficiently by
calculating lower bounds from a cost matrix and pruning paths that exceed the current
best tour cost. This reduces the number of paths explored compared to brute-force
methods.

🧮 Step 1: Cost Matrix Setup

Let’s a ssume a sample 4-city cost matrix (you can replace this with your actual
matrix):

A B C D
A ∞ 10 15 20
B 10 ∞ 35 25
C 15 35 ∞ 30
D 20 25 30 ∞

Each cell C [i][ j]represents the cost from city i to city j . Diagonal entries are ∞ to
prevent revisiting the same city.

📉 Step 2: Initial Lower Bound Calculation

 We reduce the matrix to estimate the minimum cost:

Row Reduction: Subtract the smallest value in each row.

Column Reduction: Subtract the smallest value in each column.

Initial Lower Bound = Sum of all reductions

This gives a baseline cost for the root node (starting city).

🌲 Step 3: Branching
From the root node (say, starting at A), we branch to all other cities (B, C, D). For
each branch:

Update the matrix:

Set row of current city and column of next city to ∞

Set reverse path to ∞ to prevent cycles

Recalculate lower bound for the new matrix

Add cost of the edge taken to the lower bound

✂️Step 4: Pruning
Maintain a global variable min_cost for the best complete tour found so far.

If a node’s lower bound + path cost > min_cost, prune it.

If it’s less, continue branching from that node.

This avoids exploring paths that cannot yield better solutions.

✅ Step 5: Completion
When a complete tour is found (visiting all cities and returning to start), update
min_cost if the total cost is lower.

Repeat until all nodes are either explored or pruned.

EX:

Step 1: Initial Matrix Reduction

Row Reduction:
 A: min = 10 → subtract 10 from row A
 B: min = 10 → subtract 10 from row B
 C: min = 15 → subtract 15 from row C
 D: min = 20 → subtract 20 from row D
Column Reduction:
 A: min = 0 → no change
 B: min = 0 → no change
 C: min = 0 → no change
 D: min = 0 → no change
Initial Lower Bound = 10 + 10 + 15 + 20 = 55
Step 2: Branching from Node A
We branch from A to B, C, and D. For each branch:
A → B:
 Add cost: 10
 Update matrix:
o Row A and column B set to ∞
o B → A set to ∞
 Reduce matrix again and calculate new lower bound
 Total cost = 10 + new lower bound
Repeat similarly for A → C and A → D.
✂️Step 3: Bounding and Pruning
 Keep track of the minimum cost tour found so far.
 If a branch’s total cost (path cost + lower bound) exceeds this, prune it.
 Explore only branches with promising lower bounds.
✅ Step 4: Completion
 When a complete tour is formed (visiting all cities and returning to A), compare its
cost to the current minimum.
 Update if it’s lower.
 Continue until all paths are either completed or pruned.
📌 Final Result
Let’s say the optimal tour is: A → B → D → C → A Total cost = 80
This is the shortest possible route visiting all cities once and returning to the start.

____________END___________