Brute-Force and Greedy Algorithm Design Patterns

1. Brute-Force Search

Definition

A brute-force (exhaustive search) algorithm systematically tries every possible solution until it finds one that is correct (or determines no solution exists).

Characteristics

• Exhaustive: Considers all possibilities in the search space
• Guaranteed correct: Will always find the optimal solution if one exists
• Simple to implement: Requires minimal problem-specific knowledge
• Exponential complexity: Search space grows exponentially with input size

When to Use Brute-Force

• The problem is small enough that exhaustive search is feasible
• No better algorithm is known (or it is too complex to implement)
• Correctness is more important than efficiency

Example: Finding the Longest Path

ALGORITHM LongestPath(graph, start, end)
    // Generate all possible paths, return the longest
    allPaths ← GenerateAllPaths(graph, start, end)
    return max(length(p) for p in allPaths)

For a graph with $n$ nodes, there could be up to $n!$ paths — factorial growth.

Complexity

For a problem with $n$ elements:
- Permutations: $O(n!)$
- Subsets: $O(2^n)$
- Pairs: $O(n^2)$

KEY TAKEAWAY: Brute-force guarantees correctness but is only feasible for small inputs. For large inputs, exponential/factorial complexity makes it impractical — this motivates better design patterns.

2. Greedy Algorithm Design Pattern

Definition

A greedy algorithm makes a sequence of choices, each time selecting the locally optimal (best-looking) option at that moment, without reconsidering previous choices.

Characteristics

• Locally optimal choices: Each step takes the best immediate option
• No backtracking: Once a choice is made, it is never undone
• Efficient: Often $O(n \log n)$ or better
• Not always globally optimal: Greedy choices may not lead to the best overall solution
• Correct for specific problems: When the greedy choice property and optimal substructure hold, greedy is optimal

Greedy Choice Property

A globally optimal solution can be reached by making locally optimal choices. This must be proven for greedy to be applicable.

Examples of Greedy Algorithms in VCE Algorithmics

Prim’s Algorithm — Greedy in Action

ALGORITHM Prim(graph, start)
    mst ← {}
    visited ← {start}
    while visited ≠ all vertices do
        edge ← cheapest edge from visited to unvisited vertex
        add edge to mst
        add new vertex to visited
    end while
    return mst

Each step adds the minimum-weight edge that expands the MST — a greedy choice.

Comparison: Brute-Force vs. Greedy

EXAM TIP: When asked to compare brute-force and greedy, address: (1) strategy, (2) optimality guarantee, (3) computational complexity, and (4) suitability for the given problem.

COMMON MISTAKE: Greedy is NOT always optimal. Always check whether the problem has the greedy choice property before applying it. A classic counterexample is the coin-change problem with non-standard denominations.