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):
- Sort points by x-coordinate
- Divide into left half & right half
- Compute upper & lower hull recursively
- 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)
- Greedy Choice Property: Local optimum leads to global
- 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!