1.19 Pseudocode Style

Pseudocode is a bridge between the problem statement and an implementation. It should expose the algorithmic idea without committing too early to language-specific details. Good pseudocode is precise enough to analyze, but simple enough to read as a description of the method.

The purpose of pseudocode is not to look like code. Its purpose is to make control flow, data flow, invariants, and cost visible.

Problem

You need to describe an algorithm in a way that supports correctness reasoning, complexity analysis, and later implementation.

Solution

Write pseudocode with explicit inputs, outputs, state updates, and loop boundaries.

Use this structure:

algorithm_name(input):
  initialize state

  while or for condition:
    inspect current state
    update state

  return output

For recursive algorithms:

algorithm_name(input):
  if base case:
    return direct answer

  split or reduce input
  solve smaller subproblem
  combine result
  return answer

Example: Linear Search

Poor pseudocode:

look through the array and find x

This hides the return convention and the failure case.

Better pseudocode:

contains(A, x):
  for i = 0 to length(A) - 1:
    if A[i] == x:
      return true

  return false

This version states the scan order, the condition for success, and the result when no match exists.

Example: Binary Search

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

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

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

  return false

The interval convention is clear: both left and right are inclusive. The update rules preserve that convention. The termination condition left > right means the interval is empty.

Style Rules

Use meaningful variable names. Names such as left, right, best, current, dist, and parent communicate the role of the state.

State boundary conventions explicitly. For arrays, say whether an interval is inclusive, half-open, or empty.

Prefer one idea per line. Avoid combining updates that should be reasoned about separately.

Keep primitive operations visible. If a step says “find minimum”, it may hide a linear scan, heap operation, or balanced tree lookup. State which one is intended when it affects complexity.

Do not include language noise unless it matters. Memory allocation, generics, imports, and error handling can be omitted unless they affect the algorithm.

Invariant-Friendly Pseudocode

Pseudocode should make the invariant easy to state.

For prefix scans, this usually means:

state represents the answer for elements before index i

So write loops in a way that exposes the processed prefix:

best = A[0]

for i = 1 to n - 1:
  best = max(best, A[i])

For search intervals, expose the remaining candidate region:

left = 0
right = n - 1

while left <= right:
  ...

For dynamic programming, expose the evaluation order:

for i = 0 to n:
  for j = 0 to m:
    compute dp[i][j] from earlier states

Handling Multiple Outputs

When an algorithm returns a witness, make that explicit.

Distance only:

return dist[t]

Path reconstruction:

path = empty list
v = t

while v is not none:
  prepend v to path
  v = parent[v]

return path

These are different output models. The second requires maintaining parent during the main algorithm.

Comments in Pseudocode

Use comments to state invariants or non-obvious choices, not to repeat the line.

Useful comment:

# All indices before left have been ruled out.

Weak comment:

# Increment left.
left = left + 1

The first explains why an update is safe. The second repeats syntax.

Common Pitfalls

Do not write pseudocode so vague that different readers could implement different algorithms.

Do not make pseudocode so language-specific that the algorithmic structure is hidden by syntax.

Do not omit failure cases. Every valid input should lead to a defined output.

Do not hide expensive work behind words such as “choose”, “find”, “update”, or “optimize” without saying how the work is done.

Takeaway

Good pseudocode is precise, analyzable, and implementation-ready. It states the algorithm’s state, control flow, boundary conventions, and return behavior while avoiding unnecessary language detail.