📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS (UNIT 3 – DIVIDE & CONQUER AND GREEDY METHODS) university of allahabad

 

🔴 UNIT 3 – DIVIDE & CONQUER AND GREEDY METHODS

---

🔹 PART A: DIVIDE AND CONQUER

---

1️⃣ Divide and Conquer Technique

✅ Definition

Divide and Conquer is an algorithm design technique that:

1. Divides the problem into smaller subproblems

2. Conquers them recursively

3. Combines the solutions

---

General Form:

Divide → Conquer → Combine

---

Examples:

✔ Merge Sort
✔ Quick Sort
✔ Binary Search
✔ Matrix Multiplication

---

2️⃣ Matrix Multiplication

🔹 Normal Method

Time Complexity:

O(n³)

---

🔹 Strassen’s Matrix Multiplication

Reduces multiplication operations.

Time Complexity:

O(n^2.81)

Advantage:

✔ Faster than normal method
✔ Used in large matrix computation

---

3️⃣ Convex Hull

✅ Definition

Convex Hull is the smallest convex polygon that encloses all points.

---

Algorithms:

1. Graham’s Scan

2. Jarvis March

---

Applications:

• Image processing

• Pattern recognition

• GIS systems

---

🔹 PART B: GREEDY METHOD

---

4️⃣ Greedy Algorithm

✅ Definition

Greedy algorithm chooses the best option at each step hoping to get the global optimum.

---

Characteristics:

✔ Simple
✔ Fast
❌ May not give optimal solution always

---

5️⃣ Fractional Knapsack Problem

Problem:

Maximize profit with weight constraint.

Solution:

• Take full item if possible

• Take fraction if needed

Time Complexity:

O(n log n)

✔ Greedy works here
❌ Not applicable for 0/1 knapsack

---

6️⃣ Minimum Spanning Tree (MST)

Definition:

A spanning tree with minimum total edge weight.

---

🔹 1. Prim’s Algorithm

Steps:

1. Start with any vertex

2. Select minimum weight edge

3. Add to tree

4. Repeat

Time Complexity:

O(E log V)

---

🔹 2. Kruskal’s Algorithm

Steps:

1. Sort edges by weight

2. Add smallest edge

3. Avoid cycle

Uses:

✔ Union-Find
✔ Greedy technique

---

Difference: Prim vs Kruskal

Prim	Kruskal
Vertex-based	Edge-based
Uses priority queue	Uses sorting
Dense graphs	Sparse graphs

---

7️⃣ Single Source Shortest Path

---

🔹 Dijkstra’s Algorithm

Purpose:

Find shortest path from source to all vertices.

Condition:

✔ No negative edges

Time Complexity:

O(V²)

---

🔹 Bellman-Ford Algorithm

Advantage:

✔ Handles negative weights

Disadvantage:

❌ Slower than Dijkstra

Time Complexity:

O(VE)

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 3)

✔ Explain Divide and Conquer
✔ Explain Strassen’s matrix multiplication
✔ Explain Greedy method
✔ Difference between Prim and Kruskal
✔ Explain Dijkstra algorithm
✔ Explain Fractional Knapsack