Techniques

Algorithm design strategies. Knowing them as a vocabulary helps recognize when a problem fits one.

Divide and Conquer

Break the problem into independent subproblems, solve recursively, combine. The strategy underneath mergesort, quicksort, binary search, and many matrix algorithms. The Master Theorem gives the asymptotic cost of recurrences of the form T(n) = a · T(n/b) + f(n).

• Mergesort, split, sort halves, merge.

• Quicksort, partition, sort each side.

• Binary search, the half not containing the target is discarded.

• Strassen’s matrix multiplication, O(n^2.81), a divide-and-conquer on submatrices.

• Closest pair of points, O(n log n) by splitting on x-coordinate.

The Master Theorem gives the asymptotic cost of recurrences of the form T(n) = a · T(n/b) + f(n). Useful for analyzing many divide-and-conquer algorithms quickly.

Dynamic Programming (DP)

When a problem has optimal substructure (the optimum to the whole problem combines optima of subproblems) and overlapping subproblems, solve each subproblem once and remember the answer. DP is mostly recognition; the work is in noticing the pattern. Two styles.

• Top-down (memoization), recursion + cache. Easier to write.

• Bottom-up (tabulation), iterative; usually faster, sometimes smaller space.

Classic problems.

Problem	Complexity	Application
Fibonacci	O(n)	Demo
0/1 knapsack	O(nW)	Resource allocation
Unbounded knapsack	O(nW)	Coin change variants
Longest increasing subsequence	O(n log n)	Stocks, sequence analysis
Longest common subsequence	O(nm)	Diff
Edit distance	O(nm)	Spell-check, DNA alignment
Matrix chain multiplication	O(n³)	Compiler / DB query plans
Subset sum	O(n · S)	NP-hard (pseudo-polynomial)
Traveling salesman (DP)	O(n² · 2ⁿ)	Held-Karp; small n
Bellman-Ford	O(VE)	Shortest path with neg weights
Floyd-Warshall	O(V³)	All-pairs shortest path

DP recipes.

1. Identify the state, the parameters that uniquely identify a subproblem.

2. Identify transitions, how a state reduces to other states.

3. Identify base cases.

4. Choose top-down or bottom-up.

5. Optimize space if possible (often only the last few rows / values are needed).

DP is mostly recognition. The work is in noticing that the problem fits the pattern.

Greedy

At each step, take the locally optimal choice. Hope (or prove) the global optimum follows. Greedy works on a specific class of problems (matroid-like exchange property); when it doesn’t, you usually need DP or search instead. Provability matters; “this seems right” isn’t an algorithm.

When greedy works.

• The problem has a matroid structure or a similar exchange property.

• Or you’ve proven it by induction or exchange argument.

Classic greedy algorithms.

• Activity / interval scheduling, sort by end time; pick earliest ending compatible activity.

• Huffman coding, combine the two least-frequent symbols repeatedly.

• Kruskal’s MST, always add the cheapest non-cycle-creating edge.

• Prim’s MST, always extend by the cheapest edge to a new vertex.

• Dijkstra’s shortest path, always extract the cheapest unsettled vertex.

• Fractional knapsack, sort by value-per-weight, take greedily.

Common greedy traps:

• 0/1 knapsack, greedy fails; you need DP.

• Coin change with non-standard coin systems, greedy fails.

When in doubt, prove the greedy choice property; otherwise use DP or search.

Backtracking

Build candidate solutions incrementally; abandon a partial solution (“backtrack”) as soon as it can’t lead to a valid full solution. Essentially DFS through the space of partial solutions; pruning is what turns it from “search every combinatorial possibility” into something practical.

Classic problems.

• N-Queens, place queens row by row; prune by column / diagonal conflicts.

• Sudoku solver, fill cell by cell; prune by constraint propagation.

• Subset / permutation generation, choose / don’t choose; swap-based.

• Graph coloring, try a color, recurse, undo on failure.

• CSP solvers, arc consistency, then backtrack with constraint propagation.

Backtracking is essentially DFS through the space of partial solutions. Pruning (recognizing dead-end partials early) is what makes it practical.

Branch and Bound

Backtracking plus an upper- or lower-bound estimate for partial solutions. If the bound proves a partial solution can never beat the best complete solution found so far, prune without exploring further. The standard tool for exact NP-hard optimization at small instance sizes.

• If a partial solution’s bound is worse than the best complete solution found so far, prune.

• Used for NP-hard optimization (TSP, knapsack, integer programming) when exact answers are required and the instance is small.

Randomized Algorithms

Use randomness for correctness or speed. The two flavors (Las Vegas, always correct with random runtime; and Monte Carlo, with bounded error probability) cover most of the design space. Randomization defeats adversarial inputs and provides sublinear-space approximations.

• Las Vegas, always correct; runtime is random (e.g., randomized quicksort).

• Monte Carlo, bounded error probability (e.g., Miller-Rabin primality).

Examples.

• Randomized quicksort, avoids adversarial worst case.

• Reservoir sampling, pick k uniform random items from a stream.

• Bloom filter, probabilistic set membership.

• Random projection / LSH, approximate nearest neighbor.

• Karger’s min cut, O(V²) per iteration, succeed with probability 1/V², repeat.

Approximation Algorithms

For NP-hard problems, accept a near-optimal answer in polynomial time. The approximation ratio is the proven worst-case bound; practical performance is often much better than the proof guarantees. Common results.

• Vertex cover (2-approximation), maximal matching gives a vertex cover at most 2× optimal.

• Set cover (greedy), O(log n)-approximation.

• TSP with metric edges, 1.5-approximation via Christofides.

• Bin packing, First-Fit-Decreasing achieves ~11/9 of optimal.

The approximation ratio is the proven worst-case bound; practical performance is often much better.

Streaming / Sketch Algorithms

Approximate answers in one pass over data, with sublinear memory. The standard tools for telemetry, log processing, and high-throughput databases where exact answers would require storing every distinct value, and “approximately right” is genuinely good enough.

• Count-Min sketch, approximate counts of items.

• HyperLogLog, approximate count-distinct (cardinality).

• Bloom filter, set membership.

• Reservoir sampling, random sample of unknown-size stream.

• Misra-Gries, heavy hitters.

Used in databases, log processing, networking, real-time analytics.

Two Pointers / Sliding Window / Prefix Sums

Idiomatic patterns rather than algorithms. Recognizing when a problem reduces to one of these saves substantial work – they’re each linear time and trivially implementable, and they show up in a surprising number of array problems.

• Two pointers, on a sorted array, advance pointers based on comparisons. O(n) after sorting.

• Sliding window, variable-size window; O(n) total because each pointer moves at most n times.

• Prefix sums, pre-compute cumulative sums for O(1) range-sum queries.

Recognizing when a problem reduces to one of these saves a lot of time.

Bit Manipulation

The bit tricks that come up in performance kernels, flag- heavy code, and competitive programming. The categories below cover the patterns operators meet most often, including power-of-two checks, bit toggle/set/clear, popcount, and subset enumeration over a bitmask.

• Powers of two, x & (x - 1) == 0.

• Toggle / set / clear bit, x ^= (1 << i) / x |= (1 << i) / x &= ~(1 << i).

• Count set bits, popcount; built-in on modern CPUs.

• Subset enumeration, iterate over all subsets of a bitmask.

• Bitsets, fast Boolean operations over many flags.

The classic interview categories; production uses are mostly in flag-rich code, performance kernels, and competitive programming.

Recognizing the Pattern

Most algorithm problems reduce to one of these patterns plus a data structure. Recognizing the pattern is the skill that separates “I’ll write a clever for-loop” from “this is a classic DP problem with an O(nm) solution.” The mapping below is the lookup that operators reach for under time pressure.

• “Find the optimal X over choices” → DP or greedy.

• “All combinations / permutations” → backtracking.

• “Shortest / cheapest path” → BFS / Dijkstra / Bellman-Ford.

• “Range queries on an array” → segment / Fenwick tree, prefix sums.

• “Substring problems” → suffix structures, two pointers, sliding window.

• “Approximate / streaming” → sketch algorithms.

• “Constraint satisfaction” → CSP / backtracking with propagation.

Catalog references: CLRS (Introduction to Algorithms), Skiena (Algorithm Design Manual), Erickson (Algorithms).