complete UNIT III – Divide & Conquer + Greedy Methods

UNIT III – QUICK SUMMARY TABLE (Draw First in Exam – 8 Marks!)

Divide & Conquer + Greedy Methods

QUICK SUMMARY TABLE

Here is your complete UNIT III – Divide & Conquer + Greedy Methods notes package
100% exam-ready | Diagrams + Code + Solved Questions | You will score 90–100!

UNIT III – QUICK SUMMARY TABLE (Draw First in Exam – 8 Marks!)

Technique Principle Time Complexity (Typical) Famous Examples
Divide & Conquer Divide → Solve subproblems → Combine T(n) = aT(n/b) + f(n) Merge Sort, Quick Sort, Strassen, Convex Hull
Greedy Locally optimal choice → Global opt Usually O(n log n) Kruskal, Dijkstra, Huffman, Activity Selection

1. DIVIDE & CONQUER – FULL THEORY + EXAMPLES

Master Theorem (Write This Table – 10 Marks Guaranteed!)

Case Condition Time Complexity Example
1 f(n) = O(nʳ) where r < log₂a Θ(nˡᵒᵍᵅ) Merge Sort (a=2,b=2,r=1)
2 f(n) = Θ(nˡᵒᵍᵅ) Θ(nˡᵒᵍᵅ log n) Strassen (a=7,b=2)
3 f(n) = Ω(nʳ) where r > log₂a Θ(f(n)) T(n)=2T(n/2)+n² → Θ(n²)

1.1 Merge Sort (Classic D&C)

Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n)

Diagram to Draw:

[8 3 7 1 9 4 6 2]
   /         \
[8 3 7 1]   [9 4 6 2]
 /   \       /   \
[8 3] [7 1] [9 4] [6 2]

1.2 Quick Sort (D&C + Partition)

Average: O(n log n) | Worst: O(n²)

Best Exam Diagram:

Array: 45 12 78 23 56 9 67 34 89 41
Pivot = 41 → Partition → [12 23 9 34] 41 [78 56 67 89 45]

1.3 Strassen’s Matrix Multiplication

Normal: 8 multiplications → O(n³)
Strassen: 7 multiplications → O(n²·⁸⁰⁷)

7 Products Formula (Write This!)
M₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)
M₂ = (A₂₁ + A₂₂)B₁₁
...
C₁₁ = M₁ + M₄ - M₅ + M₇

1.4 Convex Hull – Graham Scan / Jarvis March

Divide & Conquer Version (Most Asked):
1. Sort points by x-coordinate
2. Divide into left half & right half
3. Compute upper & lower hull recursively
4. Combine

Jarvis March (Gift Wrapping) → O(nh)

Diagram:

Points → Sort → Find leftmost → Keep turning left → Done

1.5 Binary Search (Simplest D&C)

T(n) = T(n/2) + O(1) → O(log n)

2. GREEDY METHOD – FULL NOTES

Greedy Properties (Write This)

  1. Greedy Choice Property: Local optimum leads to global
  2. Optimal Substructure

Famous Greedy Algorithms

Algorithm Greedy Choice Proof Idea
Activity Selection Pick activity with earliest finish time Always safe
Kruskal MST Pick smallest edge that doesn’t form cycle Cut property
Dijkstra Pick closest unvisited vertex No negative edges
Huffman Coding Merge two smallest frequency nodes Prefix code property
Fractional Knapsack Pick highest value/weight ratio Can take fraction

Activity Selection – MOST ASKED (15 Marks)

Question:
Activities: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)
Select maximum activities.

Greedy Solution:
Sort by finish time → (1,4), (3,5), (5,7), (5,9), (6,10), (8,11), (8,12), (0,6), (3,9), (2,14), (12,16)

Pick: (1,4) → (5,7) → (8,11) → (12,16) → 4 activities

Diagram:

Time: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
      [1------4]     [5---7]   [8----11]     [12------16]

C CODE EXAMPLES (Write in Practical)

// Activity Selection
#include<stdio.h>
void activitySelection(int start[], int finish[], int n) {
    printf("Selected: 0 ");
    int last = 0;
    for(int i=1; i<n; i++) {
        if(start[i] >= finish[last]) {
            printf("%d ", i);
            last = i;
        }
    }
}

15-MARKS SOLVED QUESTIONS (Copy in Exam!)

Q1. Solve 0/1 Knapsack using Greedy vs Dynamic (5+5)
→ Greedy fails! Example: capacity=10, items (v=60,w=10), (v=100,w=20), (v=120,w=30)
Greedy picks first → 60
DP picks second+third → 220

Q2. Explain Strassen with 2×2 example (10 marks)
→ Draw 4 quadrants → show 7 multiplications

Q3. Convex Hull using Divide & Conquer (12 marks)
→ Draw points → divide → merge upper/lower hull

Q4. Prove Activity Selection is optimal using Greedy
→ "Suppose optimal has activity A not in greedy. Replace A with greedy’s earlier-finishing activity → still valid and not worse."

You now have complete Unit III – ready for 100/100!

Want handwritten PDF + all diagrams? Reply “SEND UNIT III PDF”
Next unit? Say “UNIT IV” or “BACKTRACKING”! Good luck – you’ll top the class!

Last updated: Nov 28, 2025

complete UNIT III – Divide & Conquer + Greedy Methods

UNIT III – QUICK SUMMARY TABLE (Draw First in Exam – 8 Marks!)

Divide & Conquer + Greedy Methods

QUICK SUMMARY TABLE

Here is your complete UNIT III – Divide & Conquer + Greedy Methods notes package
100% exam-ready | Diagrams + Code + Solved Questions | You will score 90–100!

UNIT III – QUICK SUMMARY TABLE (Draw First in Exam – 8 Marks!)

Technique Principle Time Complexity (Typical) Famous Examples
Divide & Conquer Divide → Solve subproblems → Combine T(n) = aT(n/b) + f(n) Merge Sort, Quick Sort, Strassen, Convex Hull
Greedy Locally optimal choice → Global opt Usually O(n log n) Kruskal, Dijkstra, Huffman, Activity Selection

1. DIVIDE & CONQUER – FULL THEORY + EXAMPLES

Master Theorem (Write This Table – 10 Marks Guaranteed!)

Case Condition Time Complexity Example
1 f(n) = O(nʳ) where r < log₂a Θ(nˡᵒᵍᵅ) Merge Sort (a=2,b=2,r=1)
2 f(n) = Θ(nˡᵒᵍᵅ) Θ(nˡᵒᵍᵅ log n) Strassen (a=7,b=2)
3 f(n) = Ω(nʳ) where r > log₂a Θ(f(n)) T(n)=2T(n/2)+n² → Θ(n²)

1.1 Merge Sort (Classic D&C)

Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n)

Diagram to Draw:

[8 3 7 1 9 4 6 2]
   /         \
[8 3 7 1]   [9 4 6 2]
 /   \       /   \
[8 3] [7 1] [9 4] [6 2]

1.2 Quick Sort (D&C + Partition)

Average: O(n log n) | Worst: O(n²)

Best Exam Diagram:

Array: 45 12 78 23 56 9 67 34 89 41
Pivot = 41 → Partition → [12 23 9 34] 41 [78 56 67 89 45]

1.3 Strassen’s Matrix Multiplication

Normal: 8 multiplications → O(n³)
Strassen: 7 multiplications → O(n²·⁸⁰⁷)

7 Products Formula (Write This!)
M₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)
M₂ = (A₂₁ + A₂₂)B₁₁
...
C₁₁ = M₁ + M₄ - M₅ + M₇

1.4 Convex Hull – Graham Scan / Jarvis March

Divide & Conquer Version (Most Asked):
1. Sort points by x-coordinate
2. Divide into left half & right half
3. Compute upper & lower hull recursively
4. Combine

Jarvis March (Gift Wrapping) → O(nh)

Diagram:

Points → Sort → Find leftmost → Keep turning left → Done

1.5 Binary Search (Simplest D&C)

T(n) = T(n/2) + O(1) → O(log n)

2. GREEDY METHOD – FULL NOTES

Greedy Properties (Write This)

  1. Greedy Choice Property: Local optimum leads to global
  2. Optimal Substructure

Famous Greedy Algorithms

Algorithm Greedy Choice Proof Idea
Activity Selection Pick activity with earliest finish time Always safe
Kruskal MST Pick smallest edge that doesn’t form cycle Cut property
Dijkstra Pick closest unvisited vertex No negative edges
Huffman Coding Merge two smallest frequency nodes Prefix code property
Fractional Knapsack Pick highest value/weight ratio Can take fraction

Activity Selection – MOST ASKED (15 Marks)

Question:
Activities: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)
Select maximum activities.

Greedy Solution:
Sort by finish time → (1,4), (3,5), (5,7), (5,9), (6,10), (8,11), (8,12), (0,6), (3,9), (2,14), (12,16)

Pick: (1,4) → (5,7) → (8,11) → (12,16) → 4 activities

Diagram:

Time: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
      [1------4]     [5---7]   [8----11]     [12------16]

C CODE EXAMPLES (Write in Practical)

// Activity Selection
#include<stdio.h>
void activitySelection(int start[], int finish[], int n) {
    printf("Selected: 0 ");
    int last = 0;
    for(int i=1; i<n; i++) {
        if(start[i] >= finish[last]) {
            printf("%d ", i);
            last = i;
        }
    }
}

15-MARKS SOLVED QUESTIONS (Copy in Exam!)

Q1. Solve 0/1 Knapsack using Greedy vs Dynamic (5+5)
→ Greedy fails! Example: capacity=10, items (v=60,w=10), (v=100,w=20), (v=120,w=30)
Greedy picks first → 60
DP picks second+third → 220

Q2. Explain Strassen with 2×2 example (10 marks)
→ Draw 4 quadrants → show 7 multiplications

Q3. Convex Hull using Divide & Conquer (12 marks)
→ Draw points → divide → merge upper/lower hull

Q4. Prove Activity Selection is optimal using Greedy
→ "Suppose optimal has activity A not in greedy. Replace A with greedy’s earlier-finishing activity → still valid and not worse."

You now have complete Unit III – ready for 100/100!

Want handwritten PDF + all diagrams? Reply “SEND UNIT III PDF”
Next unit? Say “UNIT IV” or “BACKTRACKING”! Good luck – you’ll top the class!

Last updated: Nov 28, 2025