Algorithm Design Techniques — Divide, Greedy, DP

Algorithm Design Techniques

Algorithm design techniques are standard problem-solving strategies used to build efficient algorithms. Instead of inventing a new method for every problem, we study a small set of powerful techniques and learn when to apply each one.

These techniques are important because many problems in sorting, searching, optimization, graphs, and recursion follow common patterns. Once you recognize the pattern, choosing the right technique becomes much easier.

Why Do We Need Design Techniques?

Different problems require different ways of thinking. A direct brute-force solution may be correct, but it is often too slow for large input sizes. Design techniques help us create solutions that are:

• Systematic: We follow a proven method instead of guessing.
• Efficient: We reduce unnecessary work and repeated computation.
• Scalable: The solution continues to work for larger inputs.
• Easier to analyze: Time and space complexity become easier to understand.

How to Choose the Right Technique

Before selecting a technique, ask the following questions:

• Can the problem be divided into smaller problems of the same type?
• Do subproblems overlap and repeat?
• Does a locally best choice always help build the final optimal answer?
• Do we need to try many possibilities and reject invalid ones?
• Can we prune large parts of the search space using bounds or conditions?

The answers to these questions often directly point to divide and conquer, dynamic programming, greedy, backtracking, or branch and bound.

1. Divide and Conquer

Divide and Conquer solves a problem by splitting it into smaller independent subproblems, solving them recursively, and combining their results.

General Steps

• Divide: Break the problem into smaller subproblems.
• Conquer: Solve each subproblem recursively.
• Combine: Merge the smaller solutions into the final answer.

When it works well: When subproblems are independent and the combine step is efficient.

Common examples: Merge Sort, Quick Sort, Binary Search, Strassen Matrix Multiplication.

public class BinarySearch {

    static int search(int[] arr, int low, int high, int target) {
        if (low > high) {
            return -1;
        }

        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (target < arr[mid]) {
            return search(arr, low, mid - 1, target);
        }

        return search(arr, mid + 1, high, target);
    }

    public static void main(String[] args) {
        int[] arr = {3, 8, 14, 19, 27, 31, 42, 56};
        System.out.println(search(arr, 0, arr.length - 1, 27));
        System.out.println(search(arr, 0, arr.length - 1, 10));
    }
}

/*
Analysis
- Each step cuts the search space into half
- Time Complexity: O(log n)
- Space Complexity: O(log n) due to recursion
*/

2. Greedy Method

Greedy algorithms build a solution step by step by always choosing the option that looks best at the current moment. The choice is not reconsidered later.

Two Important Conditions

• Greedy choice property: A local optimum leads toward a global optimum.
• Optimal substructure: An optimal solution contains optimal solutions to subproblems.

When it works well: Scheduling, minimum spanning trees, shortest path with non-negative weights, data compression.

Main limitation: Greedy is fast, but it does not always guarantee the best answer.

public class ActivitySelection {

    static void selectActivities(int[] start, int[] finish) {
        int n = start.length;
        int last = 0;

        System.out.println("Selected activities:");
        System.out.println("Activity 0");

        for (int i = 1; i < n; i++) {
            if (start[i] >= finish[last]) {
                System.out.println("Activity " + i);
                last = i;
            }
        }
    }

    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        selectActivities(start, finish);
    }
}

/*
Greedy idea:
- Always choose the activity that finishes earliest
- This leaves maximum room for future activities
*/

3. Dynamic Programming

Dynamic Programming (DP) is used when a problem has repeated subproblems. Instead of solving the same subproblem again and again, we store the result and reuse it.

Core Properties

• Overlapping subproblems: The same smaller problems appear many times.
• Optimal substructure: The optimal solution can be built from optimal solutions of smaller parts.

Main Approaches

• Memoization: Top-down recursion with storage.
• Tabulation: Bottom-up table building.

When it works well: Knapsack, Fibonacci, LCS, matrix chain multiplication, shortest path in weighted graphs.

public class FibonacciDP {

    static long fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));
        System.out.println(fibonacci(50));
    }
}

/*
Analysis
- Naive recursion: O(2^n)
- DP version: O(n)
- Extra space: O(n)
*/

4. Backtracking

Backtracking tries to build a solution step by step. If a partial solution becomes invalid, the algorithm undoes the last choice and tries another path.

Backtracking Pattern

• Choose: Make one possible decision.
• Explore: Continue recursively.
• Unchoose: Undo the decision if it does not work.

When it works well: Constraint satisfaction problems, permutations, combinations, puzzles, path finding.

Main limitation: The worst-case time is often exponential, but pruning can still make it practical.

public class Permutations {

    static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void generate(char[] arr, int index) {
        if (index == arr.length) {
            System.out.println(new String(arr));
            return;
        }

        for (int i = index; i < arr.length; i++) {
            swap(arr, index, i);
            generate(arr, index + 1);
            swap(arr, index, i);
        }
    }

    public static void main(String[] args) {
        generate("ABC".toCharArray(), 0);
    }
}

5. Branch and Bound

Branch and Bound is an advanced search technique used mainly for optimization problems. It is similar to backtracking, but instead of exploring every possibility blindly, it calculates a bound for each partial solution.

How It Works

• Branch: Divide the problem into subproblems.
• Bound: Estimate the best possible result from each subproblem.
• Prune: Ignore a branch if it cannot beat the current best solution.

When it works well: Travelling Salesman Problem, assignment problem, integer programming, 0/1 Knapsack.

Compared to plain backtracking, branch and bound usually prunes more aggressively because it uses a numerical estimate of how good a branch can still become.

6. Randomized Algorithms

Randomized algorithms use random choices as part of their logic. The goal is usually to improve average performance, simplify the method, or avoid specially crafted worst-case inputs.

Why Randomization Helps

• It can reduce the chance of consistently bad inputs.
• It may produce good expected performance even when deterministic methods struggle.
• It is useful in approximation, simulation, and probabilistic checking.

Examples: Randomized Quick Sort, randomized selection, Monte Carlo algorithms, Las Vegas algorithms.

Comparison of Major Techniques

Technique Selection Guide

Common Mistakes While Learning These Techniques

• Using greedy without proving that the greedy choice is always safe.
• Confusing divide and conquer with dynamic programming.
• Applying dynamic programming even when subproblems do not overlap.
• Forgetting the "undo" step in backtracking.
• Ignoring space complexity while optimizing time complexity.
• Using branch and bound without a useful bounding function.

Key Takeaways

• Algorithm design techniques are reusable strategies for solving classes of problems.
• Divide and conquer works by splitting, solving, and combining.
• Greedy is fast and simple, but only works for suitable problems.
• Dynamic programming is ideal when subproblems overlap.
• Backtracking and branch and bound are powerful for search and optimization.
• Randomized algorithms improve expected behavior using probability.
• The best technique depends on the structure of the problem, not personal preference.

What to Study Next

After understanding algorithm design techniques, the next useful topic is asymptotic notation. It helps you measure and compare how efficient each technique really is as the input size grows.