Algorithm Selection Guide

Quick Decision Framework

Step 1: Identify Problem Type

Optimization Problems:

• Keywords: "minimum", "maximum", "optimal", "best"
• Look for: objective function to optimize

Constraint Satisfaction:

• Keywords: "valid configuration", "satisfying rules", "no two can..."
• Look for: constraints that must be met

Search/Traversal:

• Keywords: "find path", "reachable", "connected"
• Look for: graph or tree structure

Counting Problems:

• Keywords: "number of ways", "how many", "count"
• Look for: combinatorial enumeration

Problem Pattern Recognition

Dynamic Programming Signals

Recognition Patterns:

• Optimal substructure exists
• Overlapping subproblems present
• Memoization can help
• Keywords: "optimal", "minimum/maximum", "count ways"

Examples:
• "Find LONGEST common subsequence"
• "What's MINIMUM cost to..."
• "How many WAYS to achieve..."
• "Is it POSSIBLE to partition..."

Quick Test: Can you solve smaller versions optimally and build up?

Greedy Algorithm Signals

Recognition Patterns:

• Local optimal choice leads to global optimum
• Greedy choice property exists
• Exchange argument can prove correctness
• Keywords: "schedule", "select maximum", "earliest/latest"

Examples:
• "Schedule MAXIMUM number of activities"
• "Choose coins for MINIMUM count"
• "Select items by RATIO/PRIORITY"

Quick Test: Does choosing the best option at each step work?

Backtracking Signals

Recognition Patterns:

• Constraints must be satisfied
• Placement/arrangement problems
• Exhaustive search needed
• Keywords: "place N items", "all valid configurations", "no conflicts"

Examples:
• "Place N queens with NO attacks"
• "Find ALL solutions to puzzle"
• "Color graph with NO adjacent same colors"

Quick Test: Do you need to try all possibilities with constraints?

Divide & Conquer Signals

Recognition Patterns:

• Large problem can be split
• Independent subproblems
• Combine solutions easily
• Keywords: "sort", "search", "merge", "split"

Examples:
• "Sort large array efficiently"
• "Find element in sorted data"
• "Multiply large numbers"

Quick Test: Can you split problem into independent parts?

Algorithm Comparison Matrix

Time Complexity vs Input Size

Problem Type → Algorithm Mapping

Decision Tree for Complex Problems

Multi-Stage Decision Process

Problem Analysis
├── Optimization?
│   ├── Yes → Has Optimal Substructure?
│   │   ├── Yes → Overlapping Subproblems?
│   │   │   ├── Yes → Dynamic Programming
│   │   │   └── No → Divide & Conquer
│   │   └── No → Greedy Choice Property?
│   │       ├── Yes → Greedy Algorithm
│   │       └── No → Heuristic/Approximation
│   └── No → Constraint Satisfaction?
│       ├── Yes → All Solutions Needed?
│       │   ├── Yes → Backtracking
│       │   └── No → Constraint Propagation
│       └── No → Search/Traversal?
│           ├── Yes → Graph Algorithms
│           └── No → Analyze Further

Algorithm Selection Examples

Example 1: Coin Change Problem

Problem: "Find minimum coins to make amount X"

Analysis:

• Optimization problem (minimize coins)
• Optimal substructure (optimal for X uses optimal for X-coin)
• Overlapping subproblems (same amounts computed multiple times)

Decision: Dynamic Programming

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

Example 2: Activity Selection

Problem: "Schedule maximum non-overlapping activities"

Analysis:

• Optimization problem (maximize activities)
• Greedy choice (earliest finish time always good)
• Local optimum = global optimum

Decision: Greedy Algorithm

def activity_selection(activities):
    # Sort by finish time
    activities.sort(key=lambda x: x[1])

    selected = [activities[0]]
    last_finish = activities[0][1]

    for start, finish in activities[1:]:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish

    return selected

Example 3: N-Queens Problem

Problem: "Place N queens on board with no attacks"

Analysis:

• Constraint satisfaction (no attacks)
• Need all valid placements
• Must try all possibilities

Decision: Backtracking

def solve_n_queens(n):
    def is_safe(board, row, col):
        # Check column and diagonals
        for i in range(row):
            if (board[i] == col or
                board[i] - i == col - row or
                board[i] + i == col + row):
                return False
        return True

    def backtrack(board, row):
        if row == n:
            return [board[:]]

        solutions = []
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                solutions.extend(backtrack(board, row + 1))

        return solutions

    return backtrack([-1] * n, 0)

Performance Considerations

When Input Size Matters

Small Input (n ≤ 20):

• Backtracking is feasible
• Brute force acceptable
• Focus on correctness over efficiency

Medium Input (20 < n ≤ 1000):

• $O(n^2)$ algorithms acceptable
• Avoid exponential algorithms
• Consider space-time tradeoffs

Large Input (n > 1000):

• $O(n \log n)$ or better required
• Memory efficiency important
• Consider parallel algorithms

Space vs Time Tradeoffs

High Memory Available:

• Use memoization extensively
• Cache intermediate results
• Trade space for time

Low Memory Available:

• Use iterative over recursive
• Rolling arrays for DP
• In-place algorithms

Red Flags and Green Lights

Algorithm Red Flags

Avoid These Patterns:

• Nested loops without early termination
• Recursive calls without memoization
• Sorting inside loops
• String concatenation in loops
• Frequent dynamic memory allocation

Example of What NOT to Do:

# BAD: O(n²) with string concatenation
def bad_join(strings):
    result = ""
    for s in strings:  # O(n)
        result += s    # O(n) each time
    return result

# GOOD: O(n) with proper joining
def good_join(strings):
    return "".join(strings)

Algorithm Green Lights

Prefer These Patterns:

• Single pass algorithms when possible
• Early termination conditions
• Space optimization techniques
• Built-in data structures
• Divide and conquer for large problems

Quick Reference Checklist

Before implementing, ask yourself:

1. What's the input size range?
2. Is this an optimization problem?
3. Are there constraints to satisfy?
4. Do subproblems overlap?
5. Can I use a greedy approach?
6. Do I need all solutions or just one?
7. What's more important: time or space?

Rule of Thumb: Start with the simplest solution that works, then optimize if needed.