1.20 Implementation Discipline

Implementation discipline means translating an algorithm into code without changing its meaning accidentally. The pseudocode gives the structure. The implementation must preserve the same state, boundaries, invariants, and output contract.

Many algorithmic bugs are not failures of the idea. They are failures of translation: an inclusive interval becomes half-open, an index update skips an element, a comparison uses < instead of <=, or an integer type overflows. Implementation discipline exists to prevent these small changes from breaking the proof.

Problem

You have a correct algorithm on paper and need to implement it in a way that preserves correctness, complexity, and edge-case behavior.

Solution

Implement from the invariant outward.

Use this workflow:

1. Write the function signature from the problem statement.
2. Choose concrete data structures from the input model.
3. Encode boundary conventions directly in variable names and loop conditions.
4. Add assertions for important invariants during development.
5. Test against edge cases and a brute force baseline.
6. Check that every operation matches the claimed complexity.

The goal is to make the code look like the proof.

Example: Binary Search

A disciplined implementation starts by fixing the interval convention.

Invariant:
  If x occurs in A, then some occurrence lies in A[left..right].

This invariant uses an inclusive interval, so the loop condition must keep searching while the interval is nonempty:

while left <= right:

The updates must remove mid after it has been checked:

if A[mid] < x:
  left = mid + 1
else:
  right = mid - 1

A common implementation bug is:

left = mid

If left == mid, the interval may fail to shrink, causing an infinite loop.

A complete implementation-style pseudocode is:

binary_search(A, x):
  left = 0
  right = length(A) - 1

  while left <= right:
    mid = left + (right - left) // 2

    if A[mid] == x:
      return true

    if A[mid] < x:
      left = mid + 1
    else:
      right = mid - 1

  return false

Every assignment preserves the invariant and strictly shrinks the interval.

Boundary Conventions

Most implementation errors occur at boundaries. Choose one convention and keep it visible.

Do not mix conventions inside one function unless there is a clear reason.

Data Structure Fidelity

If the algorithm assumes constant-time indexing, implement it with an array-like structure. If it assumes fast membership, use a set or hash table. If it assumes extract-min, use a priority queue.

Example:

Dijkstra requires repeatedly extracting the unsettled vertex with minimum tentative distance.

A plain list implementation may still be correct, but it changes the complexity. The data structure is part of the algorithm, not an afterthought.

Numeric Discipline

Check numeric ranges before choosing types.

Example:

n <= 10^6
A[i] <= 10^9

A sum can reach:

10^15

This exceeds a 32-bit signed integer. The implementation should use a wider integer type.

For midpoint calculation, prefer:

mid = left + (right - left) // 2

over:

mid = (left + right) // 2

in languages with fixed-width integers.

Assertions

Assertions are useful when they encode invariants.

For binary search:

assert 0 <= left
assert right < length(A)

For a heap:

assert parent priority <= child priority

For dynamic programming:

assert dependencies of dp[i][j] have already been computed

Assertions should check meaning, not just syntax.

Complexity Preservation

After implementation, recheck the claimed complexity. Look for hidden costs.

Examples:

Using list.pop(0) in a language where it shifts all elements may turn O(n) queue logic into O(n^2).

Sorting inside a loop may add an extra logarithmic or linear factor.

Copying an array slice in each recursive call may increase both time and space.

The implemented algorithm, not the pseudocode, determines the actual cost.

Common Pitfalls

Do not change interval conventions during translation.

Do not assume library operations have the cost you want. Check whether an operation is constant, logarithmic, or linear.

Do not ignore overflow because the pseudocode uses mathematical integers.

Do not use shared mutable state in recursive code unless the invariant includes it.

Do not optimize before the baseline implementation is tested.

Takeaway

Implementation discipline preserves the proof inside the code. Fix the contract, choose data structures that match the algorithm, keep boundary conventions consistent, and check hidden costs. A correct algorithm becomes reliable software only when its implementation respects the same invariants.