📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS (UNIT 4 – DYNAMIC PROGRAMMING & BACKTRACKING) university of allahabad

 

🔴 UNIT 4 – DYNAMIC PROGRAMMING & BACKTRACKING

---

🟦 PART A: DYNAMIC PROGRAMMING

---

1️⃣ Dynamic Programming (DP)

✅ Definition

Dynamic Programming is a technique used to solve problems by:
✔ Breaking them into subproblems
✔ Solving each subproblem only once
✔ Storing results for future use

---

🔹 Properties of DP

1. Optimal Substructure

2. Overlapping Subproblems

---

2️⃣ 0/1 Knapsack Problem

Problem Statement:

Given:

• Weight array w[]

• Profit array p[]

• Capacity W

Goal:
Maximize profit without exceeding capacity.

---

DP Formula:

DP[i][w] = max(
    DP[i-1][w],
    DP[i-1][w - wi] + pi
)

---

Time Complexity:

O(nW)

---

Difference: Fractional vs 0/1 Knapsack

Feature	Fractional	0/1
Item division	Allowed	Not allowed
Approach	Greedy	Dynamic
Optimal	Yes	Yes

---

3️⃣ Matrix Chain Multiplication

Purpose:

Find the most efficient way to multiply matrices.

---

DP Formula:

M[i][j] = min{ M[i][k] + M[k+1][j] + pi-1 * pk * pj }

---

Time Complexity:

O(n³)

---

4️⃣ All-Pairs Shortest Path

---

🔹 Floyd–Warshall Algorithm

Used to find shortest paths between all pairs of vertices.

Formula:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][k])

Time Complexity:

O(n³)

---

5️⃣ Longest Common Subsequence (LCS)

Definition:

Find the longest sequence common to two strings.

---

Example:

X = ABCDGH
Y = AEDFHR
LCS = ADH

---

DP Formula:

if X[i] == Y[j]:
    L[i][j] = 1 + L[i-1][j-1]
else:
    L[i][j] = max(L[i-1][j], L[i][j-1])

---

6️⃣ Traveling Salesman Problem (TSP)

Problem:

Find the shortest path visiting each city exactly once and returning to start.

---

Solution:

✔ Dynamic Programming
❌ NP-Hard Problem

---

🟦 PART B: BACKTRACKING & BRANCH AND BOUND

---

7️⃣ Backtracking

Definition:

Backtracking tries all possibilities and removes those which fail.

---

Applications:

• N-Queen problem

• Graph coloring

• Subset sum

---

8️⃣ N-Queen Problem

Goal:

Place N queens on NxN chessboard so that:

• No two queens attack each other

---

Approach:

✔ Place queen row by row
✔ Backtrack when conflict occurs

---

9️⃣ Graph Coloring

Objective:

Color graph vertices such that:

• No adjacent vertices have same color

---

🔟 Sum of Subsets

Objective:

Find subsets whose sum equals target value.

---

1️⃣1️⃣ Branch and Bound

Definition:

Optimization technique that:

• Uses bounds

• Prunes unnecessary branches

---

Used In:

✔ Traveling Salesman
✔ Job Assignment
✔ Knapsack

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 4)

✔ Explain Dynamic Programming
✔ Solve 0/1 Knapsack
✔ Explain Floyd Warshall
✔ LCS with example
✔ N-Queen problem
✔ Branch and Bound