Other algorithmic patterns¶

This chapter is a compact index of patterns that do not need a full survey in the core path. Start from the problem's constraints and prefer standard-library or maintained implementations.

Backtracking¶

Backtracking explores a decision tree and abandons partial candidates that cannot lead to a valid solution.

choose → test partial constraints → recurse → undo

Use it for small combinatorial spaces, constraint problems, and enumeration where pruning is effective.

Correct state handling matters:

every choice must be undone exactly once;
pruning must reject only candidates that cannot succeed;
duplicate input may require duplicate-choice suppression;
recursion depth and total search can still be exponential.

Order constrained variables and promising values first only as a heuristic; it changes search time, not correctness. For small cases, compare produced solutions with exhaustive enumeration.

Branch and bound¶

Branch and bound searches optimization choices while pruning a branch when its best possible completion cannot beat the current solution.

The bound must be valid. A tighter bound prunes more but may cost more to compute. This is useful for exact optimization when instances are moderate and a general solver is not already appropriate.

Divide and conquer¶

Divide and conquer:

splits a problem into smaller mostly independent instances;
solves them recursively;
combines their results.

Examples include merge sort, binary search, and spatial algorithms. Runtime is often expressed by a recurrence such as:

\[ T(n)=aT(n/b)+f(n) \]

where \(a\) is subproblem count, \(n/b\) is subproblem size, and \(f(n)\) is split/combine work. Use a recursion tree or an applicable recurrence theorem; do not apply the Master Theorem when subproblem sizes or recurrence shape violate its assumptions.

Two pointers¶

Two-pointer algorithms maintain two positions whose movement discards impossible regions.

Common forms:

opposite ends of sorted data;
slow and fast positions for in-place compaction;
two sequences advanced according to key comparison;
cycle detection with different traversal speeds.

The proof must explain why moving one pointer cannot discard a valid answer. Sorting may be a precondition and its cost belongs to the algorithm.

Sliding windows¶

A sliding window maintains an aggregate over a contiguous range while its boundaries move.

fixed-size window: add the entering element and remove the leaving element;
variable-size window: expand until a condition changes, then shrink while restoring it.

Variable-window logic usually needs a monotonic property. For example, shrinking based on a sum threshold works cleanly for non-negative values but can fail when negative values make the sum non-monotonic.

State what the window aggregate represents and update it exactly when boundaries move.

Disjoint-set union¶

Disjoint-set union (union-find) maintains a partition under:

find(x): return the representative of \(x\)'s set;
union(a, b): merge two sets.

Path compression plus union by rank or size gives near-constant amortized operations, commonly written \(O(\alpha(n))\).

Use it for undirected connectivity under edge additions, Kruskal's algorithm, and grouping equivalence relationships. It does not support general edge deletion or path reconstruction without additional machinery.

String searching¶

Use the language's substring search first. Choose specialized structures only from a workload:

Need	Candidate
One pattern in one text	library search
Guaranteed linear scan for one pattern	KMP-style prefix automaton
Probabilistic filtering or many equal-length windows	rolling hash with equality verification
Many patterns scanned together	trie or Aho-Corasick
Prefix lookup	trie or ordered index
Many substring queries on static text	suffix array/index or search engine

Text algorithms must define the unit: bytes, Unicode code points, or user-perceived grapheme clusters. Normalization and case folding are domain decisions, not incidental preprocessing.

Hash equality is not string equality unless the hash scheme provides a stronger contract; verify candidate matches when collisions are possible.

Bit manipulation¶

Bit operations are appropriate for masks, compact sets, binary protocols, and fixed-width representations.

Common identities for non-negative or fixed-width values include:

test bit \(i\): x & (1 << i);
set bit \(i\): x | (1 << i);
clear bit \(i\): x & ~(1 << i) within the declared width;
remove lowest set bit: x & (x - 1);
isolate lowest set bit: x & -x under two's-complement semantics.

Prefer built-ins such as integer bit count and bit length. Avoid XOR-swap and similar tricks that are less clear than ordinary assignment and rarely improve generated code.

Always specify width, signedness, shift behavior, and byte order at serialization boundaries.

Randomized algorithms¶

Randomization can improve expected performance, sampling, or resistance to adversarial structure.

Distinguish:

Las Vegas: result is correct; runtime is random;
Monte Carlo: runtime is bounded; result has a quantified error probability.

Examples:

randomized pivot selection for selection or sorting;
reservoir sampling of a fixed-size sample from a stream of unknown length;
probabilistic membership structures such as Bloom filters.

A Bloom filter can report false positives but, under its normal insertion-only contract and correct implementation, not false negatives. Deletion requires a different design. Record capacity and target error assumptions; saturation changes behavior.

Tests should accept a deterministic random source or seed for reproducibility without claiming one seed validates the distribution.

Selection and order statistics¶

Finding the \(k\)th item does not require fully sorting all input.

heap-based selection is simple when \(k\) is small or data streams;
quickselect has expected linear time but needs safeguards for adversarial behavior;
a maintained selection primitive is preferable when available.

Define whether \(k\) is zero- or one-based and how duplicates are ordered.

Pattern guide¶

Symptom	Pattern to investigate
Need all feasible assignments under constraints	backtracking or solver
Need exact optimum with useful bounds	branch and bound
Independent smaller instances combine cleanly	divide and conquer
Sorted range can be discarded from either end	two pointers
Contiguous range changes incrementally	sliding window
Repeated union and connectivity queries	disjoint-set union
Repeated prefix or substring workload	string index
Small finite state encoded compactly	bitmask, with explicit exponential bound
Stream sampling or adversarial input order	randomized method

Do not force a problem into a named pattern. Write the invariant, preconditions, and complexity first; the label is only vocabulary.

Validation¶

For any custom algorithm:

test minimal, boundary, duplicate, and invalid inputs;
state the invariant and termination argument;
compare small cases with brute force or a trusted implementation;
generate adversarial as well as random inputs;
measure increasing sizes under the actual representation;
replace it with a standard implementation when the custom behavior is not required.