S034 · Greedy & Backtracking — When to Use Each

Module M03: Data Structures & Algorithms · Session 34 of 130 · Track: SW 🪜

What you'll be able to do after this session

• Explain Greedy & Backtracking to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S033 — Dynamic Programming — Memoisation & Tabulation

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Greedy Algorithms — Abdul Bari — clearest 10-minute intro; walks through the activity-selection classic.
• 🎥 Deep dive (30–60 min) · MIT 6.046 Lecture — Greedy Algorithms & MST — proves why greedy works for MST (exchange argument).
• 🎥 Hands-on demo (10–20 min) · NeetCode — Backtracking Pattern (Subsets, Permutations, N-Queens) — one template that solves all three.
• 📖 Canonical article · CP-Algorithms — Backtracking (N-Queens) — canonical write-up + pruning tricks.
• 📖 Book chapter / tutorial · Kleinberg & Tardos, Ch. 4: Greedy Algorithms (Cornell notes) — the book most CS professors teach from.
• 📖 Engineering blog · Uber Eng — Kraken: How Uber Uses Real-Time Optimisation — greedy load-balancing at fleet scale.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Two more decision-making patterns.

Greedy = "at every step, do what looks best right now and never look back." Making change for ₹87 with Indian coins? Grab a ₹50, then a ₹20, then a ₹10, then a ₹5, then two ₹1s — six coins, done. You never reconsider. Greedy is fast (usually O(n log n) — one sort + one pass) but only correct when the "locally best move is always globally optimal" property holds. With Indian coins it does; with a bizarre currency of {1, 3, 4} and target 6, greedy picks 4+1+1 (3 coins) but the optimum is 3+3 (2 coins). That failure is why we needed DP in the previous session.

Backtracking = "try every option, undo when it doesn't work." It's brute force with a rewind button — build a solution piece by piece, and the moment a partial solution can't possibly extend to a valid full solution, throw it away and try the next branch. Sudoku solvers, N-queens, all-permutations, regex .* matching, parsing — all backtracking. Slower than greedy (worst-case exponential) but complete: it finds a solution if one exists.

The mental split: greedy is a bet (fast but risky — must prove correctness), backtracking is exhaustive search with pruning (slow but always right). DP sits between them: it explores all subproblems but stores answers to avoid re-work.

The forever gotcha: if you can't prove your greedy choice is safe (exchange argument or matroid theory), assume it's wrong and reach for DP or backtracking. Interview problems love to look greedy and secretly not be.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Greedy — Activity Selection. You have meeting slots and want to attend the maximum number of non-overlapping meetings.

Meetings (start, end): (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16).

Greedy rule: sort by end time, then repeatedly pick the earliest-ending meeting that starts after the last picked one ends.

Answer: 4 meetings. The exchange argument: any optimal solution can be rewritten to start with the earliest-ending meeting without losing meetings — so the greedy choice is safe.

Backtracking — N-Queens (n=4). Place 4 queens on a 4×4 board so no two attack each other.

Solution: queens at (0,1), (1,3), (2,0), (3,2).

Key: the moment a partial placement has no safe square in the next row, prune — don't explore any deeper.

When to use which — decision table:

Classic greedy successes: Dijkstra, Prim's MST, Kruskal's MST, Huffman coding, fractional knapsack, activity selection, interval-point covering.

Classic backtracking successes: N-queens, Sudoku, all subsets/permutations, Hamiltonian path, boolean SAT (with clause learning → modern SAT solvers), constraint satisfaction problems.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Save as gb_lab.py and run with python3 gb_lab.py:

# ---------- GREEDY: activity selection ----------
def activity_selection(meetings):
    """Return max set of non-overlapping meetings. meetings = [(start, end), ...]."""
    meetings = sorted(meetings, key=lambda m: m[1])   # sort by end time
    chosen, last_end = [], -1
    for s, e in meetings:
        if s >= last_end:
            chosen.append((s, e))
            last_end = e
    return chosen
 
# ---------- GREEDY: coin change (works for canonical currencies only!) ----------
def coin_change_greedy(coins, amount):
    coins = sorted(coins, reverse=True)
    used = []
    for c in coins:
        while amount >= c:
            amount -= c; used.append(c)
    return used if amount == 0 else None
 
# ---------- BACKTRACKING: N-queens ----------
def n_queens(n):
    solutions, placed = [], []  # placed[r] = col of queen in row r
 
    def safe(r, c):
        for pr, pc in enumerate(placed):
            if pc == c or abs(pc - c) == abs(pr - r):
                return False
        return True
 
    def solve(r):
        if r == n:
            solutions.append(placed.copy()); return
        for c in range(n):
            if safe(r, c):
                placed.append(c)
                solve(r + 1)
                placed.pop()          # ← the "backtrack"
 
    solve(0)
    return solutions
 
# ---------- BACKTRACKING: all subsets (power set) ----------
def all_subsets(nums):
    out, cur = [], []
    def solve(i):
        if i == len(nums):
            out.append(cur.copy()); return
        solve(i + 1)                  # skip nums[i]
        cur.append(nums[i]); solve(i + 1); cur.pop()   # include nums[i]
    solve(0)
    return out
 
if __name__ == "__main__":
    meetings = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
    print("Activities:", activity_selection(meetings))
 
    print("Coins for 87 (Indian):", coin_change_greedy([1,2,5,10,20,50,100,500], 87))
    print("Coins for 6 (weird [1,3,4]) — greedy:", coin_change_greedy([1,3,4], 6))
    # ^ greedy picks 4+1+1 (3 coins) — optimum is 3+3 (2 coins). Greedy FAILS here.
 
    print("4-queens solutions:", n_queens(4))              # 2 solutions
    print("8-queens count:", len(n_queens(8)))             # 92
    print("subsets of [1,2,3]:", all_subsets([1,2,3]))     # 8 subsets

Checklist — observe when you run:

1. Activity selection picks 4 meetings — matches Layer b's worked table.
2. Greedy coin change works for {1,2,5,10,20,50,100,500} (Indian denominations are canonical). It fails for {1,3,4} returning 3 coins when optimal is 2. This is the "greedy isn't always right" lesson.
3. n_queens(4) returns 2 distinct placements; n_queens(8) returns 92 — well-known result.
4. all_subsets([1,2,3]) returns 2³ = 8 subsets. This is backtracking's cost: exponential in input size.
5. Increase to n_queens(12) — still fast (under a second) thanks to safe() pruning. Remove the pruning (always call solve(r+1)) and it becomes intractable.

Try this modification: modify n_queens to stop at the first solution instead of enumerating all. How much faster is it for n=12? (Hint: return True/False up the recursion.)

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Greedy in production is everywhere:

• Ride matching (Uber, Lyft, Ola). Match the nearest driver to the nearest request every few seconds — pure greedy on a bipartite graph. Optimal batch matching would be Hungarian algorithm O(n³), but greedy is fast enough at scale, and users perceive "instant match" as higher quality than "wait 4 seconds for optimal."
• CDN cache eviction (LRU, LFU). Every cache in your stack — Cloudflare, Redis, browser HTTP cache — uses a greedy policy: evict whichever item's local score is worst. Not provably optimal (Belady's algorithm is offline-optimal), but 99% of the practical value.
• Compilers. Register allocation via graph colouring is NP-hard; production compilers (LLVM, GCC) use greedy heuristics that produce near-optimal code in linear time.
• Task schedulers (Kubernetes). The default scheduler scores every node greedily against each pod and picks the highest.

Backtracking in production:

• Regex engines. Perl, Python re, JavaScript regex — all backtracking. That's why (a+)+b on input aaaaaaaaaaaaaaaaaaaaX takes exponential time. Google's RE2 engine replaces backtracking with a Thompson NFA to guarantee linear time — at the cost of dropping backreferences. Cloudflare's famous 2019 global outage was a catastrophic-backtracking regex.
• SAT / SMT solvers. Z3, MiniSat — modern chip verification, program analysis, and even LLM-guided theorem proving depend on smart backtracking (DPLL + clause learning).
• Type inference. Haskell / Rust / TypeScript type checkers backtrack when they can't unify types.

Common bugs:

• Assuming greedy is correct without proof. Coin change with arbitrary denominations, task scheduling with dependencies — both look greedy, both need DP.
• Backtracking without pruning. N-queens without the safe() check works but is 100× slower. Always ask: "can I detect failure earlier?"
• Mutating shared state without undo. Backtracking bugs #1 — you push into a list, recurse, but forget to pop on the way out. Rule of thumb: every append needs a matching pop; every set needs a matching restore. Or, use immutable arguments.
• Regex catastrophic backtracking. Never trust user-supplied regex. Set a time budget or migrate hot paths to RE2.

The senior-engineer tell: they always ask "is there a counterexample where greedy fails?" before writing the loop, and they always add a depth argument to backtracking for debugging + timeouts.

(e) Quiz + exercise · 10 min

1. Give one problem where greedy works and one similar-looking problem where it fails.
2. What's the key structural property that makes greedy safe (name and one-line definition)?
3. Describe backtracking in one sentence, and explain why pruning is what makes it practical.
4. For activity selection, why do we sort by end time and not by start time or by duration?
5. Name two real production systems whose bugs / performance disasters were traced to catastrophic backtracking.
6. Stretch (connects to S033 Dynamic Programming): Coin change with denominations {1, 3, 4} and target 6. Show why greedy returns 3 coins while DP returns 2. Then explain what feature of DP allows it to "see further ahead" than greedy.

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Greedy & Backtracking? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S035): The Relational Model — Tables, Keys, Normalisation
• Previous (S033): Dynamic Programming — Memoisation & Tabulation
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.