Greedy Technique Notes & Formulas

1. Foundational Definitions

The Greedy Technique is an algorithmic paradigm designed to solve optimization problems-scenarios requiring the determination of either a minimum or maximum result. In the rigorous landscape of the GATE Computer Science syllabus, the Greedy Method is preferred for its computational efficiency, often providing a polynomial-time alternative to the exponential costs of exhaustive search or backtracking. It operates by making a sequence of choices, constructing a solution piece by piece with an emphasis on immediate gain.

To navigate this topic with mastery, aspirants must distinguish between the following four pillars:

• Greedy Choice Property: The principle that a global optimum can be reached by making a locally optimal choice-the "best" move at the current moment-without regard for future consequences.
• Optimal Substructure: A problem exhibits this property if an optimal solution to the global problem contains within it optimal solutions to its constituent subproblems.
• Local vs. Global Optimum: A local optimum is the best choice within a specific step's feasible set. A global optimum is the absolute best solution across the entire solution space. Greedy "hopes" the former consistently leads to the latter.
• Feasible vs. Optimal Solution: A feasible solution is any subset of inputs that satisfies all problem constraints (e.g., total weight $le$ capacity). An optimal solution is a feasible solution that also achieves the best value for the objective function.

Algorithm Greedy(A, n) {
    for i = 1 to n do {
        x = Select(i);
        if feasible(x) then
            Solution = Solution + x;
    }
    return Solution;
}

Intuition Corner: The hallmark of the Greedy mindset is its irrevocable nature. Unlike Dynamic Programming or Backtracking, Greedy never reconsiders or revokes a decision once made. If an input is selected or discarded, that decision is final.

2. The Core Idea: Incremental Optimization

The "Greedy mindset" is an exercise in hope: the hope that local perfection yields global success. While Dynamic Programming systematically evaluates all subproblems to guarantee a global best, Greedy is decisively forward-looking.

Mechanics of Incremental Solution Building:
The algorithm constructs a solution vector through a sequence of steps, governed by an optimization mindset seeking the absolute minimum or maximum.

• Irrevocable Decisions: Once an element is included in the solution set, it cannot be removed. Conversely, if an element is discarded because it violates feasibility, it is never reconsidered.
• Step-by-Step Feasibility: Every selection is immediately passed through a "feasibility" check against problem constraints.
• Optimization Criteria: Choices are made based on a specific heuristic, such as highest profit per unit weight or earliest deadline.

3. Key Properties and Correctness Intuition

The mathematical validity of Greedy strategies relies on two formal pillars of proof:

1. The Exchange Argument: Assumes an optimal solution $O$ exists. If it doesn't use the Greedy choice $g$, swap an element in $O$ with $g$. Demonstrate that the solution remains optimal (or improves), proving Greedy is at least as good.
2. Staying Ahead: Demonstrates that at each step $i$, the Greedy choice is at least as good as any other strategy's choice.

Categorization of Greedy Strategies:

• Sorting-based: Pre-processing inputs (e.g., sorting jobs by profit) to allow linear selection.
• Selection-based: Dynamically selecting the "best" next item using efficient data structures like Heaps or Priority Queues.

GATE Insight: Sorting is frequently the computational bottleneck. If a Greedy algorithm requires sorting $n$ elements, its time complexity is usually dominated by $O(n log n)$.

4. General Greedy Problem-Solving Framework

To design a correct Greedy solution and avoid common exam traps, follow this 5-step framework:

1. Identify Objective: Define the target (Min/Max).
2. Local Choice: Determine the selection criterion (e.g., $p_i/w_i$ ratio).
3. Verify Property: Ensure the problem possesses the Greedy Choice and Optimal Substructure properties.
4. Prove Correctness: Use the Exchange Argument or Contradiction.
5. Analyze Complexity: Evaluate both sorting and selection costs.

Pattern-Recognition for GATE:
Look for "Min/Max" keywords combined with resource allocation or interval constraints.

Common Mistakes: The 0-1 Knapsack Trap
The Greedy ratio strategy fails for 0-1 Knapsack (where items cannot be split).
Counter-example: Item 1 ($10, 60, ratio 6), Item 2 (20, 100, ratio 5), Item 3 (30,$120, ratio 4). Capacity = 50.

• Greedy (Ratio): Picks Item 1 and Item 2 (Weight 30, Profit $160). Capacity left: 20 (cannot fit Item 3).
• Optimal (DP): Picks Item 2 and Item 3 (Weight 50, Profit $220).
  Greedy fails here because its irrevocable nature cannot "undo" the choice of Item 1 to fit more valuable combinations.

5. Greedy Strategy Patterns

Most classic problems follow these specific mathematical patterns:

| Pattern Name | Greedy Choice Criterion | Common Application |
| :--- | :--- | :--- |
| Ratio-based | Highest Profit/Weight ($p_i / w_i$) | Fractional Knapsack |
| Frequency-based | Lowest Frequency first | Huffman Coding |
| Earliest Finish | Earliest deadline/finish time | Activity Selection / Job Sequencing |
| Minimum Cost | Smallest edge weight | MST (Prim's, Kruskal's) |
| Path Length | Minimum distance from source | Dijkstra's Algorithm |

6. Time and Space Complexity Analysis

Greedy is generally more efficient than Dynamic Programming. DP often requires $O(n^2)$ or $O(n cdot W)$ space for memoization, whereas Greedy typically requires $O(n)$ or $O(1)$ extra space beyond the input.

| Algorithm | Time Complexity | Data Structure Used |
| :--- | :--- | :--- |
| Fractional Knapsack | $O(n log n)$ | Sorting |
| Huffman Coding | $O(n log n)$ | Min-Heap |
| Kruskal's MST | $O(E log E)$ or $O(E log V)$ | Min-Heap + Union-Find |
| Prim's MST (Matrix) | $O(V^2)$ | Weight Matrix + Unordered Array |
| Prim's MST (Heap) | $O(E log V)$ | Adjacency List + Min-Heap |
| Dijkstra's | $O(V^2)$ or $O(E log V)$ | Weight Matrix or Min-Heap |
| Job Sequencing | $O(n^2)$ or $O(n cdot d)$ | Gantt Chart (array-based) |

7. Paradigm Comparison: Greedy vs. DP vs. Backtracking

Choosing the wrong paradigm is a classic GATE trap.

| Feature | Greedy | Dynamic Programming | Backtracking |
| :--- | :--- | :--- | :--- |
| Decision Strategy | Local optimal choice | Global optimization | Explore all paths |
| Optimality Guarantee | Only if Greedy properties hold | Always guaranteed | Always guaranteed |
| Memory Usage | Low (Space efficient) | High (Table/Memoization) | Moderate (Recursion Stack) |
| Irrevocability | Irreversible decisions | Revisits subproblems | Can backtrack/undo |

The "So What?" Layer: In the 0-1 Knapsack problem, Greedy is faster ($n log n$) but suboptimal. DP is "slower" (Pseudo-polynomial $O(nW)$) but guarantees the best result. Always verify if the problem allows fractions before choosing Greedy.

8. Identifying Greedy Problems in GATE

Under exam pressure, utilize "The Art of Identification":

• Optimization Keywords: "Minimum spanning," "Shortest path," "Maximum profit."
• Constraints: Look for constraints that allow for incremental building, such as deadlines or capacities.
• Red Flags: 0-1 constraints (non-fractional), non-distinct weights in MST (multiple solutions possible), or arbitrary coin denominations (Greedy coin change fails for non-standard denominations).

9. Deep Dive: Classic Greedy Problems (GATE Critical)

• Fractional Knapsack:
  • Greedy Choice: Sort by $p_i/w_i$.
  • GATE Twist: If items are already sorted by ratio, the complexity is $O(n)$.
  • Constraint: $0 le x_i le 1$.
• Job Sequencing with Deadlines:
  • Constraints: Non-preemptive, Uniprocessor, All arrival times are 0.
  • Greedy Choice: Sort by profit descending; place job in the latest available slot before or at its deadline.
  • Complexity: $O(n^2)$ if max deadline $d=n$.
  • Solution Space: There are $2^n$ possible subsets for $n$ jobs.
• Huffman Coding:
  • Mechanism: Uses a Min-Heap. BUILD-MIN-HEAP takes $O(n)$; the $n-1$ mergers (each with two EXTRACT-MIN operations) take $O(n log n)$.
  • Property: Prefix-free-no codeword is a prefix of another.
  • GATE Twist: A 100,000-character file with 6 characters. Fixed-length (requires $lceil log_2 6 ceil = 3$ bits) = 300,000 bits. Huffman (variable) might use only 224,000 bits-a ~25% saving.
• Optimal Merge Pattern:
  • Greedy Choice: Always merge the two smallest sorted files.
  • Logic: Total record movements = $\sum f_i d_i$, where $f_i$ is the number of records (frequency) and $d_i$ is the depth from the root.
  • Solution Space: For $n$ files, there are $n!$ possible merge patterns.
• MST: Prim's vs. Kruskal's:
  • Prim's: Grows a single connected tree from a root vertex. $O(V^2)$ with weight matrix; $O(E log V)$ with min-heap.
  • Kruskal's: Grows a forest that eventually connects. Always acyclic but usually disconnected in intermediate stages. $O(E log E)$.
  • Selection: Kruskal's is preferred for sparse graphs ($E = O(V)$); Prim's is better for dense graphs ($E = O(V^2)$).
• Dijkstra's Algorithm:
  • Logic: Shortest paths are generated in increasing order of path length.
  • Constraint: Requires non-negative edge weights.

10. Proof Techniques and Theoretical Intuition

• Exchange Argument: Assume an optimal solution $O$ exists. If it doesn't use the Greedy choice $g$, swap an element in $O$ with $g$. If the result is not worse, Greedy stays optimal.
• Staying Ahead: Show that for every $k$, the Greedy solution is "at least as far along" as any other solution. Dijkstra's is a prime example: paths are found in strictly non-decreasing order.

11. Advanced Concepts & Implementation

Performance is dictated by data structure choice.

• Min-Heaps: Essential for Huffman, Optimal Merge, and Heap-based MST/Dijkstra.
• Union-Find (Disjoint Set): Vital for Kruskal's to detect cycles in $O(\alpha(V))$ time.
• Online vs. Offline: Most GATE problems are "Offline" (all data known upfront). Online algorithms must make choices as data arrives.

12. Common GATE PYQ Patterns and Traps

• Sorting Traps: Ensure you know the order. Job Sequencing = Profit Descending. Optimal Merge = File Size Ascending.
• MST Uniqueness: If all edge weights are distinct, the MST is unique. If weights are non-distinct, multiple MSTs may exist, but the total cost remains the same.
• Huffman Bit Logic: Practice calculating bits saved. Formula: $( ext{Fixed bits} imes ext{Total chars}) - \sum ( ext{Freq}_i imes ext{CodeLength}_i)$.

13. Fast Revision Notes: The Greedy Cheat Sheet

Complexity Summary:

• Fractional Knapsack: $O(n log n)$ (or $O(n)$ if sorted).
• Job Sequencing: $O(n cdot d)$ or $O(n^2)$.
• Huffman/Optimal Merge: $O(n log n)$.
• Kruskal's: $O(E log E)$ or $O(E log V)$.
• Prim's/Dijkstra: $O(V^2)$ (Matrix) or $O(E log V)$ (Heap).

Quick Identification Checklist:

• Optimization: Seeking Min/Max?
• Substructure: Can the problem be broken down?
• Independence: Does the current best choice affect feasibility but not the optimality of future choices?
• Failure Check: Does it have 0-1 constraints (Knapsack) or non-standard denominations (Coin Change)? If yes, use DP.

High-Yield Facts:

• Job Sequencing Solution Space: $2^n$ subsets.
• Optimal Merge Solution Space: $n!$ patterns.
• MST Property: Distinct weights $implies$ Unique MST.
• Prim's vs Kruskal's: Prim's is a tree (connected); Kruskal's is a forest (disconnected).