Classic Algorithms: Divide‑Conquer, DP, Greedy, Backtracking, Branch‑and‑Bound

Today I randomly found my old university textbook "Algorithm Design and Analysis" and decided to review several classic algorithms, summarizing their key concepts.

Divide‑and‑Conquer

Basic idea : Break a problem into independent smaller subproblems, solve each recursively, and combine their solutions.

Applicable problem features :

The problem becomes easy to solve once its size is reduced sufficiently.

The problem exhibits optimal substructure.

The subproblems are independent (no overlapping subproblems).

Key points :

How to decompose the problem into smaller instances with the same solution method.

The granularity of decomposition.

Steps : Decompose → Recursively solve → Merge.

divide-and-conquer(P) {
    if (|P| <= n0) adhoc(P); // solve small case
    divide P into smaller subinstances P1,P2,...,Pk; // split
    for (i = 1; i <= k; i++) {
        yi = divide-and-conquer(Pi); // solve subproblems
    }
    return merge(y1,...,yk); // combine results
}

Google’s core MapReduce algorithm is a derivative of divide‑and‑conquer.

Example: Merge Sort (illustrated below).

Dynamic Programming

Basic idea : Decompose the problem into overlapping subproblems, store solutions to subproblems, and reuse them to avoid redundant computation.

Applicable problem features :

Optimal substructure.

Repeated subproblems in recursive computation.

Steps :

Identify the property of optimal solutions and characterize the substructure.

Define the optimal value recursively.

Compute the optimal values bottom‑up.

Construct the optimal solution from the computed information.

Greedy Algorithms

Basic idea : Make the locally optimal choice at each step, hoping to reach a globally optimal solution.

Applicable problem features :

Greedy‑choice property: a global optimum can be built from a sequence of local optima.

Optimal substructure.

Steps : Repeatedly select the best local option.

Examples: coin change, Huffman coding, single‑source shortest path, minimum spanning tree (Prim and Kruskal).

Backtracking

Basic idea : Perform depth‑first search of the solution space tree, pruning branches that cannot lead to a solution.

Applicable problem features : The solution space can be represented as a tree that is easy to explore.

Steps :

Define the solution space.

Identify a searchable structure.

Search depth‑first, using a pruning function to discard invalid branches.

Example: N‑Queens problem.

Branch‑and‑Bound

Basic idea : Explore the solution space using breadth‑first or best‑first (minimum cost) strategies, expanding each active node once and discarding branches that cannot improve the current best solution.

Example: Single‑source shortest path problem in a directed graph with non‑negative edge weights.