Comparison of Algorithm Paradigms

1. Greedy Algorithm

• Basic Concept: Makes locally optimal choices in the hope of finding a global optimum.
• Classification: Optimization problems with greedy-choice property & optimal substructure.
• Applications: Huffman Coding, Kruskal’s & Prim’s MST, Dijkstra’s shortest path, Activity selection.
• Advantages: Simple, fast, easy to implement, efficient when applicable.
• Disadvantages: Not always optimal, limited applicability, requires proof of greedy-choice property.

2. Dynamic Programming (DP)

• Basic Concept: Breaks problems into overlapping subproblems, solves each once, and stores results.
• Classification: Optimization problems with overlapping subproblems & optimal substructure.
• Applications: Fibonacci, Knapsack, Matrix Chain Multiplication, LCS, Bellman-Ford.
• Advantages: Guarantees optimal solution, reduces exponential to polynomial, efficient reuse of results.
• Disadvantages: High memory, slower than greedy when greedy applies, needs careful formulation.

3. Divide and Conquer (D&C)

• Basic Concept: Breaks a problem into smaller independent subproblems, solves recursively, and combines results.
• Classification: Recursive paradigm with independent subproblems & merge step.
• Applications: Merge Sort, Quick Sort, Binary Search, Strassen’s multiplication, Closest pair of points.
• Advantages: Efficient (e.g. O(n log n)), recursive simplicity, parallelizable.
• Disadvantages: Recursive overhead, extra space sometimes, not ideal if subproblems overlap (DP better).

Quick Comparative Table

Aspect	Greedy	Dynamic Programming	Divide & Conquer
Concept	Local optimal choice	Store & reuse subproblems	Split → Solve → Combine
Problem Type	Optimization (special)	Optimization (general)	General recursive problems
Key Property	Greedy-choice property	Overlapping subproblems	Independent subproblems
Applications	MST, Dijkstra, Huffman	Knapsack, LCS, Bellman-Ford	Sorting, Search, Geometry
Advantages	Fast, simple	Optimal solution guaranteed	Efficient, parallelizable
Disadvantages	Not always optimal	High memory/time sometimes	Recursive overhead, extra space

apps-fileview.texmex_20250814.00_p1
Algorithms-comparison.html
Displaying Algorithms-comparison.html.