1. Algorithmic Design

Algorithmic design is the discipline of constructing principled, efficient procedures for solving computational problems. Where the analysis of algorithms asks how fast or how much memory a given algorithm uses, design asks the earlier question: how do we construct an algorithm in the first place? The two questions are inseparable in practice — a well-chosen design paradigm both structures the solution and determines its complexity.

The field rests on the observation that most computational problems, however superficially different their domains, share deep structural properties that admit recurring solution strategies. Recognising which paradigm applies to a problem — and why — is the central skill of algorithm design. Kleinberg and Tardos ¹ organise the field around a small number of such paradigms as a pedagogical framework; Skiena ² emphasises the design manual perspective, cataloguing problem types and the techniques known to work for each; Cormen et al. ³ provide the rigorous mathematical treatment. Russell and Norvig ⁴ extend this into AI search.

1.1 Three Orthogonal Axes of Classification

A persistent source of confusion in the literature is that algorithms are classified along three independent axes that are logically distinct but are often conflated:

The same algorithm can be described simultaneously from all three axes: binary search lives in the data-structures search domain, uses the divide and conquer paradigm, and is deterministic (not a search-space algorithm). A lives in the state-space / AI search domain, uses the heuristic cost-based paradigm, and is informed*. Conflating these axes — e.g. calling best-first search a "paradigm" when it is really a search strategy — leads to incoherent comparisons ⁴¹.

1.2 I. By Problem Domain

Classifying algorithms by the kind of data or structure they operate on is the most natural starting point. It maps directly to course syllabi (data structures, graph theory, optimisation) and tells you which data representation is assumed ³².

1.2.1 1. Searching in Data Structures

These algorithms search for a target element within an explicitly stored, structured collection. The key characteristic is that the data is enumerable and indexable — elements can be accessed by position or key in \(O(1)\).

1.2.1.1 Binary Search

The paradigm case for searching in data structures is binary search: given a sorted array \(A[0..n-1]\) and a target \(t\), it locates \(t\) — or confirms its absence — in \(O(\log_2 n)\) comparisons. At each step it computes the midpoint \(m_k = \ell_k + \lfloor (h_k - \ell_k) / 2 \rfloor\) and eliminates half the remaining interval by comparing \(A[m_k]\) with \(t\). From the design perspective it is a textbook instance of divide and conquer (Axis II); from the search-strategy perspective it is deterministic and uninformed (it uses no knowledge of where \(t\) might be within the sorted range beyond the sorted-order invariant).

1.2.1.2 Linear Search

Linear (sequential) search scans \(A\) left to right, comparing each element with \(t\) in turn. It requires no precondition on \(A\) and costs \(O(n)\) comparisons in the worst case. Although dominated by binary search on sorted data, it is optimal for unsorted data and is the correct choice when the collection is small, unsorted, or stored in a linked structure that does not support random access ³.

1.2.2 2. Sorting Algorithms

Sorting algorithms impose a total order on an unordered sequence. They are foundational because many other algorithms — binary search, Kruskal's MST, many DP formulations — require sorted input.

1.2.2.1 Merge Sort (article coming soon)

Merge sort divides the array into two halves, recursively sorts each, and merges them in \(O(n)\) time. The recurrence \(T(n) = 2T(n/2) + O(n)\) solves to \(T(n) = O(n \log n)\) by the Master Theorem (see Divide and Conquer below). It is the canonical stable, comparison-based sort and the prototype for external sorting, where data does not fit in RAM ³.

1.2.3 3. Graph Algorithms

Graph algorithms operate on \(G = (V, E)\) where \(V\) is a set of nodes and \(E \subseteq V \times V\) is a set of edges. They model road networks, social graphs, dependency graphs, and state spaces.

1.2.3.1 Breadth-First Search (BFS) (article coming soon)

BFS explores \(G\) layer by layer from a source \(s\), using a FIFO queue. It visits all nodes at distance \(d\) from \(s\) before visiting any node at distance \(d+1\), and therefore finds the shortest path (minimum number of edges) between \(s\) and every reachable node in \(O(V + E)\) time. From Axis II, BFS is an uninformed search with no priority ordering beyond the FIFO queue. It is the foundation of Dijkstra's algorithm (which adds a cost-weighted priority queue) and of bidirectional search ³¹.

1.2.4 4. Optimisation Algorithms

Optimisation algorithms seek the best feasible solution under a cost metric and a set of constraints. Unlike graph algorithms, the solution need not be a path — it may be a subset, assignment, schedule, or flow.

1.2.4.1 Knapsack (DP version) (article coming soon)

The 0/1 knapsack problem asks: given \(n\) items with values \(v_i\) and weights \(w_i\), and a capacity \(W\), which subset maximises total value subject to total weight \(\leq W\)? The greedy strategy (take items by value-per-weight ratio) is optimal for the fractional knapsack but not for the 0/1 variant. Dynamic programming solves it in \(O(nW)\) time by filling a table \(\text{dp}[i][c]\) = maximum value using items \(1..i\) with capacity \(c\). This is pseudo-polynomial: exponential in the bit length of \(W\), so the problem remains NP-hard in the strong sense ³¹.

1.2.5 5. State-Space / AI Search

State-space search algorithms navigate an implicitly defined graph whose nodes are configurations (states) of a problem, and whose edges are actions or transitions. Unlike data-structure search, the graph is not stored — it is generated on the fly during exploration. This is the setting studied intensively in artificial intelligence ⁴⁵.

1.2.5.1 Greedy Best-First Search

Greedy best-first search orders its open list by \(h(n)\) — the heuristic estimate of cost from \(n\) to the goal — alone, with no accounting for the cost already paid to reach \(n\). It is fast when \(h\) is accurate but sacrifices optimality: it may return a path that is longer (more expensive) than the shortest one because it cannot distinguish cheap-to-reach nodes from expensive ones that happen to look close to the goal. From Axis II it is a greedy algorithm; from Axis III it is informed search ⁴⁶.

1.2.5.2 A*

A* combines the cost paid so far, \(g(n)\), with the heuristic, \(h(n)\), into the evaluation function \(f(n) = g(n) + h(n)\). When \(h\) is admissible — never overestimating the true cost to the goal — A* is guaranteed to expand the minimum number of nodes needed to confirm optimality among all algorithms with the same heuristic information ⁷⁶. It is both an informed search strategy (Axis III) and a heuristic cost-based paradigm (Axis II).

1.3 II. By Design Paradigm

The design paradigm describes the structural strategy used to build the algorithm, independent of the domain. This is the deeper classification: two algorithms can operate on completely different data (one on arrays, one on graphs) yet share the same paradigm — and therefore the same correctness proof technique and the same complexity analysis tools ¹³.

1.3.1 1. Divide and Conquer

Divide and conquer splits an input of size \(n\) into \(a \geq 2\) sub-problems each of size \(n/b\), solves them recursively, and combines the results in \(O(n^k)\) time. The total work satisfies the recurrence

whose solution is given by the Master Theorem ³:

Algorithms in this paradigm: binary search (\(a=1, b=2, k=0\)), merge sort (\(a=2, b=2, k=1\)), quick sort (expected), Strassen's matrix multiplication (\(a=7, b=2, k=2\)), FFT, closest-pair ¹.

1.3.2 2. Greedy Algorithms

A greedy algorithm builds a solution incrementally by making the locally optimal choice at each step, never reconsidering past decisions. Correctness is proved by one of two standard techniques:

• Greedy stays ahead: for every prefix of the greedy solution, it is at least as good as the corresponding prefix of any other feasible solution.
• Exchange argument: any optimal solution can be transformed step by step into the greedy solution without losing quality ¹.

Key concept — Greedy-choice property: a globally optimal solution can be assembled from locally optimal choices. This property must be proved; it is not universally true.

Algorithms in this paradigm: Kruskal's MST, Prim's MST, Dijkstra's shortest path (non-negative weights), Huffman coding, interval scheduling maximisation, fractional knapsack, greedy best-first search.

1.3.3 3. Dynamic Programming

Dynamic programming (DP) applies when a problem exhibits two structural properties ³¹:

• Optimal substructure: an optimal solution to the full problem contains optimal solutions to its sub-problems.
• Overlapping sub-problems: the same sub-problems recur in a naive recursive decomposition.

When both hold, sub-problem solutions are stored in a table (bottom-up) or cache (top-down memoisation) and retrieved in \(O(1)\). If there are \(P\) distinct sub-problems each solvable in \(O(W)\) given prior answers, total cost is \(O(P \cdot W)\) — often polynomial where naive enumeration is exponential.

Algorithms in this paradigm: Bellman–Ford shortest paths, Floyd–Warshall all-pairs shortest paths, 0/1 knapsack, longest common subsequence, sequence alignment (Needleman–Wunsch), matrix-chain multiplication, optimal BSTs, Viterbi algorithm ².

1.3.4 4. Backtracking

Backtracking is a systematic exhaustive-search strategy that constructs a solution incrementally and prunes partial candidates the moment they are found to violate a feasibility constraint or cannot possibly lead to a better complete solution. The search operates on an implicit tree of partial solutions; pruning eliminates entire subtrees without enumerating them.

Constraint propagation (arc consistency, forward checking) and ordering heuristics (MRV — minimum remaining values) substantially reduce the effective tree size in practice ⁴.

Algorithms in this paradigm: N-queens, Sudoku solving, graph colouring, SAT solving (DPLL), subset-sum.

1.3.5 5. Branch and Bound

Branch and bound extends backtracking to optimisation: the algorithm maintains an incumbent (best solution found so far) and computes a lower bound on the cost of any completion of a partial solution. A subtree is bounded — pruned — when its lower bound exceeds the incumbent, since no completion can improve on the current best.

The tightness of the lower bound determines efficiency, and best-first node selection (expand the node with the lowest bound) tends to find good incumbents early, maximising pruning ³².

Algorithms in this paradigm: TSP exact solvers, integer linear programming, vehicle routing.

1.3.6 6. Randomised Algorithms

Randomised algorithms introduce deliberate randomness, trading deterministic worst-case guarantees for better expected behaviour or probabilistic correctness.

• Las Vegas: always correct; running time is a random variable. Example: randomised quicksort (expected \(O(n \log n)\), worst case \(O(n^2)\)).
• Monte Carlo: fixed or bounded time; correct with high probability. Example: Miller–Rabin primality testing.

Algorithms in this paradigm: randomised quicksort, randomised BSTs, skip lists, Karger's min-cut, Miller–Rabin, randomised approximate counting ¹³.

1.3.7 7. Approximation Algorithms

For NP-hard optimisation problems, exact polynomial-time solutions are believed impossible. Approximation algorithms run in polynomial time and return a solution within a provable factor \(\alpha \geq 1\) of the optimum:

Algorithms in this paradigm: 2-approximation vertex cover, \((1-1/e)\)-approximation max coverage, PTAS/FPTAS for knapsack, \(O(\log n)\)-approximation set cover, greedy TSP ¹.

1.3.8 8. Problem Reductions

A reduction \(A \leq_p B\) is a polynomial-time transformation of any input to \(A\) into an input to \(B\) that preserves yes/no answers. Reductions are used both to design algorithms (reduce a new problem to a solved one) and to prove hardness (if \(A\) is NP-hard and \(A \leq_p B\), then \(B\) is NP-hard) ³¹.

1.4 III. By Search Strategy

This axis classifies algorithms by how much knowledge about the goal they exploit during exploration. It is most relevant for state-space / AI search but also illuminates data-structure algorithms ⁴.

1.4.1 1. Uninformed (Blind) Search

Uninformed algorithms explore the state space without any domain-specific guidance about where the goal might be. The only information used is the structure of the graph and, where applicable, edge costs.

1.4.1.1 Breadth-First Search (BFS)

BFS uses a FIFO queue to explore nodes layer by layer from the source. Because every node at depth \(d\) is visited before any at depth \(d+1\), BFS finds the shallowest (minimum-hop) path to the goal. It is complete on finite graphs and optimal for unit-cost edges, but its \(O(b^d)\) memory consumption is prohibitive for deep goals with large branching factors. IDS achieves the same optimal, complete guarantee as BFS with only \(O(bd)\) memory by iterating DFS with increasing depth limits ⁴³.

1.4.2 2. Informed (Heuristic) Search

Informed algorithms use a domain-specific heuristic function \(h(n)\) — an estimate of the cost from \(n\) to the goal — to bias exploration toward promising regions of the state space. The quality of \(h\) determines how much the algorithm improves over blind search.

A heuristic \(h(n)\) is admissible if \(h(n) \leq h^*(n)\) for all nodes \(n\), where \(h^*(n)\) is the true optimal cost to the goal. Admissibility is the condition under which A* is guaranteed to return an optimal solution. Pearl ⁶ proves that with a near-perfect heuristic the expected expansion count grows polynomially with path length, rather than exponentially as in blind search.

1.5 Cross-Reference: Where Algorithms Fit All Three Axes

1.6 Choosing a Paradigm

No single rule determines the right technique for every problem. The following questions guide the choice:

1. Does the problem have optimal substructure and overlapping sub-problems? → Dynamic programming.
2. Does a local greedy choice provably lead to global optimality? → Greedy algorithm.
3. Is the input recursively divisible into independent sub-problems? → Divide and conquer.
4. Is the problem a constraint satisfaction or combinatorial search? → Backtracking or branch and bound.
5. Is the problem NP-hard and exact optimality not required? → Approximation algorithm or heuristic.
6. Can randomness break worst-case patterns? → Randomised algorithm.
7. Can the problem be transformed into one already solved efficiently? → Reduction.
8. Is domain-specific distance information available? → Informed search (greedy best-first, A*).

Skiena ² provides a problem-type catalogue matched to techniques; Kleinberg and Tardos ¹ develop each paradigm from first principles with formal proofs; Cormen et al. ³ give the standard mathematical treatment across all paradigms.