Algorithm Design

Phase 1 — Problem framing

**Problem**: [one-paragraph precise statement]
**Inputs**:
  - [name : type, shape, valid range]
**Outputs**:
  - [name : type, guarantees]
**Constraints**:
  - [size bounds, time budget, memory cap, stability requirements]
**Correctness**: [how do we know the result is right?]
**Assumptions**: [anything taken as given]

Ask render mode per diagram-rendering mixin and output path (default: /documentation/[case]/algorithm-design/[problem-name]/).

Phase 2 — Candidate approaches

At least two candidates — compare.

Candidate A — [name]

• Idea: one paragraph
• Time: O(...)
• Space: O(...)
• Stability: stable / unstable (for sorts)
• In-place: yes / no
• Parallelizable: yes / no / partially
• Trade-offs: what it gives up

Candidate B — [name]

Same structure.

Candidate C (only if materially different)

Comparison table

Phase 3 — Chosen approach

Pick one; justify based on constraints.

Phase 4 — Invariants

What holds before, during, and after? These are the scaffolding for the correctness argument.

• Loop invariant: [e.g. "at start of iteration k, arr[0..k) is sorted"]
• Data-structure invariant: [e.g. "heap property: parent ≤ children"]
• Global invariant: [e.g. "total balance preserved across all accounts"]

Phase 5 — Pseudocode

Language-neutral; precise.

function mergeSort(arr, lo, hi):
    # precondition: 0 <= lo <= hi <= len(arr)
    # postcondition: arr[lo..hi) is sorted, permutation of original
    if hi - lo <= 1: return
    mid = lo + (hi - lo) // 2
    mergeSort(arr, lo, mid)
    mergeSort(arr, mid, hi)
    merge(arr, lo, mid, hi)

function merge(arr, lo, mid, hi):
    # buf : temporary array of size (hi - lo)
    # invariant after kth write to buf:
    #   buf[0..k) is sorted, min of remaining in arr
    ...

Annotate loops + recursion with invariants.

Phase 6 — Correctness argument

One of:

• Loop invariant proof — initialization / maintenance / termination
• Structural induction — base case + inductive step
• Preservation of invariant — show each operation preserves invariants
• Reduction — show problem reduces to a solved one

Brief + honest; formal proofs only when warranted.

Phase 7 — Edge cases

Phase 8 — Complexity analysis

• Time: worst / average / best with justification
• Space: auxiliary + in-place qualifier
• Amortized analysis if relevant (e.g. dynamic array push = O(1) amortized)
• Hidden constants if they matter (cache behavior, branch predictor)

Phase 9 — Failure + numerical concerns

• Overflow / underflow — typed arithmetic or big-int required?
• Floating-point — precision, epsilon, NaN handling, order of operations
• Cancellation — order operations to preserve stability
• Determinism — reproducible across runs / platforms?
• Concurrency — safe under races? requires lock / CAS / immutability?

Phase 10 — Test strategy

• Property-based tests: invariants hold across random inputs
• Boundary tests: every edge case above
• Performance tests: confirm target at scale
• Fuzz / differential tests: compare vs reference impl if any
• Regression tests: any historical bug inputs pinned

Examples:

PROPERTY: for any list xs, sort(sort(xs)) == sort(xs)
PROPERTY: sort(xs) is a permutation of xs
PROPERTY: adjacent elements satisfy ≤

Phase 11 — Parallelization + scale considerations

• Divide-and-conquer break points
• Memory bandwidth vs CPU
• Out-of-core (spill to disk) if input exceeds memory
• Streaming variant if input arrives incrementally
• Distributed variant boundary

Phase 12 — Alternative approaches + rejections

Same list as Phase 2 with explicit reject rationale. Keep short.

Phase 13 — Diagrams

Flow (control)

flowchart TD
    Start --> Check{size<=1?}
    Check -->|yes| Ret[return]
    Check -->|no| Split
    Split --> LeftRec[mergeSort left]
    Split --> RightRec[mergeSort right]
    LeftRec --> Merge
    RightRec --> Merge
    Merge --> Ret

Recursion / divide

graph TD
    A[n] --> B[n/2]
    A --> C[n/2]
    B --> D[n/4]
    B --> E[n/4]
    C --> F[n/4]
    C --> G[n/4]

Phase 14 — Diagram rendering

Per diagram-rendering mixin.

Phase 15 — Report assembly and approval

# Algorithm Design: [Problem]

**Date**: [date]

## Problem
## Inputs + Outputs + Constraints
## Candidate Approaches
## Comparison
## Chosen Approach
## Invariants
## Pseudocode
## Correctness Argument
## Edge Cases
## Complexity Analysis
## Failure + Numerical Concerns
## Test Strategy
## Parallelization + Scale
## Alternatives + Rejections
## Diagrams
## Hand-offs
## Assumptions & Limitations

Present for user approval. Save only after confirmation.

Assessment + planning rules

• Problem + constraints explicit
• Multiple candidates compared
• Invariants stated
• Correctness argued
• Edge cases listed
• Complexity honest
• Test strategy included
• No fabricated constraints

Failure behavior

Self-check

[] Problem + constraints stated
[] ≥2 candidate approaches
[] Complexity per candidate
[] Invariants for chosen approach
[] Correctness argued
[] Edge cases covered
[] Numerical + concurrency concerns considered
[] Test strategy proposed
[] Pseudocode precise
[] Alternatives rejected with rationale
[] Diagrams valid
[] No fabricated constraints
[] Report follows output contract