Algorithmic Patterns

Definition

An algorithmic pattern, or algorithmic paradigm, is a method, strategy, or technique of solving a problem.

Some Common Patterns

The following is just a list of common paradigms; there aren't any detailed examples here.

Divide and Conquer

Breaking down a problem into multiple independent subproblems, solving the subproblems (recursively), and combining those solutions into a solution for the original problem.

Examples:

• Mergesort
• Quicksort
• Median
• Karatsuba's Integer Multiplication
• Matrix Multiplication
• FFT
• Nearest Neighbors

Decrease and Conquer

A variant of divide and conquer where the problem is broken down into one subproblem.

Examples:

• Binary search
• Factorial
• Selection Sort
• Largest Number
• Greatest Common Divisor

The Greedy Method

Solving a problem by doing the "best looking" thing at each step.

Examples

• Minimum Spanning Trees
• Naive coin changing
• Huffman Compression

Dynamic Programming

Solving an optimization problem by breaking down a problem into multiple overlapping subproblems, solving the subproblems (recursively), and combining those solutions into a solution for the original problem.

Examples:

• Interval scheduling
• Longest common subsequence
• Coin changing
• Levenshtein distance
• Matrix-chain multiplication
• Integer knapsack
• Shortest path
• Word wrap
• Traveling salesperson

Backtracking

A method for systematically generating possible solutions to a problem in which you sometimes have to back up when realizing your paritally generated candidate can't possibly be extended to a real solution.

Examples:

• Map coloring
• Eight queens
• Knight's Tour
• Maze solving
• Regular expression matching
• Generic path finding

Branch and Bound

Backtracking applied to optimization problems.

Examples:

• Satisfiability
• Traveling salesperson
• Integer programming
• Nearest neighbor search
• Nonlinear programming

Hill Climbing

Solving (or finding an approximate solution to) an optimization problem by generating candidate solutions that are (hopefully) improvements over the previous candidate. Basic Hill Climbing chooses the "best" next step, Genetic algorithms choose a genetic mutation of the previous candidate. Simulated Annealing makes the next choice based on a particular formula used in metallurgy.

Particle Swarm Optimization

Solving an optimization problem with a bunch of decentralized particles all searching for a solution with something that looks like its has a collective organization (e.g. ant colonies, bird flocks, animal herds, etc.)

Examples:

• Neural network training
• Finite element updating

Las Vegas

A randomized algorithm that always produces the correct answer but makes no guarantees on how long it will run or how much space it will need (in the worst case).

Used as a defense against algorithm complexity attacks.

Examples:

• Finding a value in a collection
• Randomized Quicksort

Monte Carlo

A randomized algorithm that has time and space guarantees but has a small probablility of giving the wrong answer. The probability of error can be reduced by running the algorithm longer.

Used when all known deterministic algorithms for a problem are too slow, or when estimation is an inherent part of the problem.

Examples:

• Miller-Rabin primality test
• Approximating pi (by throwing darts)
• Approximating integrals
• Game playing

Reduction (Transformation)

Solving a problem by reducing, or transforming, it to a similar (usually easier) problem whose solution implies a solution to the original.