Algorithms, Proof, and Formal Reasoning

Last Updated May 30, 2026

Algorithms are not only instructions for machines. They are mathematical objects: finite procedures that transform input into output under stated assumptions. To reason seriously about an algorithm is to ask more than whether it appears to work. It is to ask what problem it solves, what inputs it accepts, what output it guarantees, why it terminates, why it is correct, how much it costs, and what its results mean in context.

Proof gives algorithmic thinking its rigor. A program may pass many tests and still fail on an unseen case. A visual example may persuade the eye but not establish the general claim. A benchmark may show performance under one workload but not prove scalability. Formal reasoning connects the procedure to a specification: if the input satisfies the preconditions, then the algorithm should terminate and produce an output satisfying the postconditions.

This article examines algorithms, proof, and formal reasoning as a central bridge between mathematical thinking and computer science. It explores algorithm specifications, preconditions, postconditions, loop invariants, induction, recursion, correctness proofs, termination, complexity, data-structure invariants, graph algorithms, formal methods, type systems, proof assistants, Haskell-style typed modeling, SQL schemas, and the responsible interpretation of formally correct computational systems.

What Algorithms Mean

An algorithm is a finite, well-defined procedure for solving a problem or transforming input into output. This definition sounds simple, but it contains several mathematical commitments. The procedure must have steps. The steps must be unambiguous. The input domain must be specified. The output must satisfy a condition. The procedure must terminate, unless the algorithm is explicitly intended to describe an ongoing process.

Algorithms are often implemented as programs, but an algorithm is not identical to its implementation. The same sorting algorithm can be written in Python, C, Haskell, Rust, Julia, or pseudocode. The implementation may differ, but the mathematical structure can remain the same: input, procedure, invariant, output, and cost.

Algorithmic reasoning begins by asking what problem is being solved. Sorting, for example, is not simply “put numbers in order.” A precise specification says that the output must be sorted and must contain exactly the same elements as the input. If an algorithm returns a sorted list but drops values, it is not correct. If it preserves all values but does not order them, it is not correct. Both conditions matter.

To think mathematically about algorithms is to treat them as objects of reasoning. They can be defined, compared, proven, optimized, refuted, bounded, generalized, and interpreted.

Back to top ↑

What Formal Reasoning Adds

Formal reasoning adds disciplined justification. It replaces informal confidence with explicit claims and supporting arguments. In everyday programming, a developer may say “this works.” Formal reasoning asks: works for which inputs, under which assumptions, according to which specification, and by what proof?

Formal reasoning does not mean abandoning intuition. Intuition often helps discover an algorithm. Examples help reveal patterns. Diagrams help clarify structure. Tests help find defects. But formal reasoning asks whether the idea can be justified for all valid cases, not only the cases already seen.

In computer science, formal reasoning appears in many forms: loop invariants, induction, structural induction, type checking, model checking, theorem proving, formal specifications, Hoare logic, temporal logic, algebraic laws, precondition/postcondition reasoning, and proof assistants. Each offers a way to connect a computational artifact to a mathematical claim.

Formal reasoning gives computer science a language for trust. It does not make systems perfect, but it clarifies what has been proven, what has only been tested, what remains assumed, and what lies outside the formal model.

Back to top ↑

Specifications, Preconditions, and Postconditions

A specification states what an algorithm or program is supposed to do. Without a specification, correctness is undefined. A program cannot be “correct” in the abstract; it can only be correct relative to a stated task, input domain, and output requirement.

Preconditions state what must be true before an algorithm runs. Postconditions state what must be true after it runs. For example, binary search requires a sorted sequence as a precondition. Its postcondition is that it returns a valid index of the target if the target is present, or a valid missing result if the target is absent. If the input is not sorted, the guarantee no longer applies.

Specifications separate responsibility. Some errors come from a flawed algorithm. Others come from invalid input. Still others come from an incomplete specification. Formal reasoning requires these distinctions. A sorting algorithm that assumes comparable elements is not responsible for inputs where comparison is undefined, unless the specification says it must handle them.

A precise specification is not bureaucracy. It is the foundation of proof. Without it, tests may pass, code may execute, and outputs may appear plausible, but there is no clear standard for correctness.

Back to top ↑

Correctness: Partial, Total, and Conditional

Correctness is often divided into partial correctness and total correctness. Partial correctness says that if the algorithm terminates, then its output satisfies the specification. Total correctness says both that the algorithm terminates and that the output satisfies the specification.

This distinction matters because an algorithm that never terminates does not produce an incorrect output; it produces no output. A loop that searches forever may preserve an invariant, but it does not solve the problem. A recursive function may be logically well-structured for valid cases but fail to reach its base case for invalid inputs. Formal reasoning separates output correctness from stopping behavior.

Correctness is also conditional. A proof depends on assumptions: input type, data-structure invariant, graph structure, sortedness, nonnegative weights, absence of overflow, reliable arithmetic, and valid model boundaries. These assumptions must be visible. Hidden assumptions are a common source of software failure.

Correctness proofs make software less mysterious. They show why a procedure works instead of merely showing that it worked once.

Back to top ↑

Loop Invariants and Stable Truths

A loop invariant is a statement that remains true before and after each iteration of a loop. It is one of the most important tools for proving algorithm correctness. A loop may change variables, move indices, update data structures, or accumulate results. The invariant identifies what is stable beneath that change.

To prove a loop invariant, one usually shows three things: initialization, preservation, and termination. Initialization shows that the invariant holds before the first iteration. Preservation shows that if it holds before an iteration, it holds after that iteration. Termination shows that when the loop stops, the invariant implies the desired postcondition.

Insertion sort provides a classic example. Before each outer-loop iteration, the processed prefix of the list is sorted. The next element is inserted into the correct position within that prefix. The invariant is preserved. When all elements have been processed, the entire list is sorted.

Invariants train a crucial mathematical habit: do not merely watch a program change; identify what remains true while it changes.

Back to top ↑

Induction and Recursive Correctness

Many algorithms are recursive, and recursive algorithms are naturally proven by induction. The proof mirrors the structure of the algorithm. A base case handles the smallest input directly. The recursive step assumes the algorithm works on smaller inputs and proves that the larger case is correct when those smaller results are combined.

Merge sort is an example. The base case is a list of length zero or one, which is already sorted. The recursive step splits the list, recursively sorts each half, and merges the sorted halves. The proof must show that the recursive calls return sorted permutations of their inputs, and that merging two sorted lists produces a sorted permutation of the combined input.

Structural induction extends this idea from numbers to recursively defined structures such as lists, trees, expressions, formulas, and syntax. If a data structure is recursive, the proof method should usually follow that recursive structure.

Induction and recursion are paired forms of reasoning. Recursion builds or computes by reducing to smaller cases. Induction proves by establishing that those reductions are valid for all cases.

Back to top ↑

Termination and Well-Founded Descent

Termination means that an algorithm eventually stops. For loops, termination often depends on a counter, index, queue, stack, or decreasing measure. For recursive algorithms, termination depends on recursive calls moving toward a base case. For graph algorithms, termination often requires tracking visited states to avoid cycling forever.

A termination proof usually identifies a measure that cannot decrease indefinitely. This may be a natural number such as list length, interval size, remaining nodes, recursion depth, or unprocessed elements. If the measure decreases on every step and cannot go below zero, the process must eventually stop.

Termination proofs are often overlooked because many programs terminate on test inputs. But test termination is not general termination. A recursive function may terminate for small examples while diverging for edge cases. A graph traversal may terminate on acyclic graphs but loop on cyclic ones unless a visited set is used. A distributed protocol may appear stable under one schedule and fail under another.

Termination is not a mere technicality. A nonterminating algorithm can consume resources, block systems, create denial-of-service conditions, or fail silently by never producing a needed result.

Back to top ↑

Complexity as Formal Cost Reasoning

Correctness answers whether an algorithm solves the problem. Complexity answers how much it costs to do so. An algorithm may be correct but impractical. A brute-force search may eventually find the answer but require exponential time. A sorting method may be easy to prove but slow on large inputs. A graph algorithm may work on small examples but fail under scale.

Complexity analysis treats time, memory, communication, and sometimes energy as mathematical functions of input size. Big-O notation abstracts from machine-specific details and focuses on growth. This allows algorithms to be compared structurally.

Complexity proofs often rely on counting operations, solving recurrences, bounding loops, estimating graph traversal costs, or analyzing data-structure operations. Complexity is itself a form of formal reasoning: a claim about resource growth that must be justified.

Complexity reasoning matters for public systems as well as technical systems. If a system scales poorly, it may become unreliable, expensive, exclusionary, or unavailable exactly when demand grows. Formal cost reasoning is part of responsible design.

Back to top ↑

Data-Structure Invariants

Data structures are not only containers. They are structures with invariants. A binary search tree requires values in the left subtree to be below the node and values in the right subtree to be above it. A heap requires each parent to satisfy an ordering condition relative to its children. A hash table requires key-bucket consistency and collision handling. A stack preserves last-in, first-out behavior.

Algorithms often rely on these invariants. Binary search requires sorted order. Heap operations require the heap property. Graph algorithms require valid adjacency representation. If the invariant is broken, the algorithm’s proof no longer applies.

Formal reasoning about data structures asks what must remain true after each operation. The invariant is the bridge between representation and reliable behavior.

Back to top ↑

Graph Algorithms and Proof Obligations

Graph algorithms make relational structure executable. Breadth-first search, depth-first search, shortest-path algorithms, topological sorting, connected-component algorithms, spanning-tree algorithms, matching algorithms, and flow algorithms all depend on graph-theoretic properties.

Each graph algorithm has proof obligations. Breadth-first search must prove that vertices are discovered in nondecreasing distance from the source. Dijkstra’s algorithm must prove that once a vertex is settled, its shortest distance is final, which depends on nonnegative edge weights. Topological sorting must prove that every edge goes from earlier to later in the output order, which depends on the graph being acyclic.

Graph algorithms also highlight interpretive responsibility. A shortest path is only as meaningful as the edge weights. A dependency order is only as meaningful as the modeled dependencies. Reachability in a graph does not automatically imply social influence, trust, causation, or permission. Formal graph correctness must be separated from domain interpretation.

Back to top ↑

Types, Contracts, and Program Structure

Types are a form of formal reasoning built into programming languages. A type constrains what values may appear and what operations are allowed. A type checker can rule out certain errors before the program runs. More expressive type systems can encode stronger structural guarantees, though no type system captures every relevant property.

Contracts are related but often more explicit. A contract may state preconditions, postconditions, invariants, or interface obligations. Types and contracts both make assumptions visible.

Algebraic data types are especially useful for formal reasoning because they make cases explicit. A result may be success or failure. A tree may be a leaf or a node. An expression may be a literal, variable, addition, multiplication, or function call. Pattern matching then forces the programmer to reason by cases.

Types cannot replace proof, testing, or ethical review. But they can bring formal structure into everyday programming and prevent many avoidable errors.

Back to top ↑

Formal Methods and Verification

Formal methods use mathematical techniques to specify, model, and verify computational systems. They include model checking, theorem proving, proof assistants, abstract interpretation, type-theoretic verification, temporal logic, Hoare logic, refinement, and formal specification languages.

Formal methods are especially important when failure is costly: avionics, medical devices, cryptographic protocols, distributed systems, operating systems, compilers, financial infrastructure, public-sector decision systems, and safety-critical embedded software. In such systems, testing alone may be inadequate because the state space is too large or the consequences of failure are too severe.

Formal methods require careful modeling. A proof about a model is only as useful as the model’s relationship to the real system. If the model omits important failure modes, timing behavior, environmental assumptions, human interaction, or deployment constraints, the proof may be formally valid but practically incomplete.

Formal verification is not magic. It shifts the burden from informal trust to explicit specification, formal modeling, and mechanically or mathematically checked reasoning.

Back to top ↑

Testing, Proof, and Evidence

Testing and proof are complementary. Testing runs a program on selected cases and observes behavior. Proof reasons from definitions to guarantees. Testing can reveal defects, validate assumptions, and expose unexpected interactions. Proof can show why certain errors cannot occur under stated conditions.

Neither testing nor proof is complete by itself. A proof may verify the wrong specification. Tests may miss the failing case. A formally verified component may still be misused by another component. A test suite may pass while a boundary case remains broken. Strong engineering cultures combine examples, property-based tests, proofs, code review, static analysis, runtime monitoring, and post-deployment feedback.

Testing asks, “What happened here?” Proof asks, “What must happen under these assumptions?” Responsible computing needs both questions.

Back to top ↑

Learning Algorithmic Proof

Learning algorithmic proof is difficult because it requires moving from concrete execution to abstract reasoning. Many learners can trace an algorithm on one input but struggle to state why it works for all inputs. They may understand code operationally but not yet see the invariant, induction structure, or specification.

Good instruction should connect examples to proofs. A trace shows what happens. A diagram shows structure. A counterexample reveals a missing condition. A specification defines the goal. An invariant explains stability. A proof generalizes beyond the example.

Algorithmic proof becomes easier when students learn to ask disciplined questions: What is the input? What is the output? What is the invariant? What decreases? What is preserved? What follows when the loop or recursion ends?

Back to top ↑

A Mathematical Lens: Specify, Prove, Analyze, Interpret

A useful lens for algorithms, proof, and formal reasoning is the sequence: specify, prove, analyze, interpret. First, specify the problem. Then prove that the procedure solves it. Then analyze the cost. Finally, interpret what the result means in context.

This lens prevents two common mistakes. The first mistake is implementation without specification: writing code before knowing precisely what it should guarantee. The second mistake is formal correctness without interpretation: proving that a system satisfies a specification without asking whether the specification is legitimate, complete, or appropriate for the real context.

Formal reasoning is strongest when it remains connected to context. It should clarify what has been proven and what has not.

Back to top ↑

Computational Companion Examples

The companion repository for this article should extend the Mathematical Thinking codebase with examples focused on algorithm specifications, proof obligations, invariants, correctness audits, termination checks, complexity growth, graph-algorithm assumptions, Haskell algebraic data types, SQL proof metadata, and responsible interpretation of algorithmic outputs. The examples below are compact article-level previews; the repository can expand them into richer professional workflows.

Python: Algorithm Specification and Invariant Audit

from dataclasses import dataclass
from collections import Counter
from typing import Sequence

@dataclass(frozen=True)
class AlgorithmSpec:
    name: str
    precondition: str
    postcondition: str
    invariant: str
    termination_measure: str
    complexity: str
    interpretation_note: str

def is_sorted(values: Sequence[int]) -> bool:
    return all(values[i] <= values[i + 1] for i in range(len(values) - 1))

def same_multiset(left: Sequence[int], right: Sequence[int]) -> bool:
    return Counter(left) == Counter(right)

def insertion_sort(values: list[int]) -> list[int]:
    result = values[:]

    for i in range(1, len(result)):
        key = result[i]
        j = i - 1

        while j >= 0 and result[j] > key:
            result[j + 1] = result[j]
            j -= 1

        result[j + 1] = key

    return result

spec = AlgorithmSpec(
    name="insertion_sort",
    precondition="input is a finite list of comparable integers",
    postcondition="output is sorted and preserves the input multiset",
    invariant="before each outer loop, the processed prefix is sorted",
    termination_measure="number of unprocessed elements decreases",
    complexity="O(n^2) worst-case time; O(1) auxiliary space",
    interpretation_note="formal sorting correctness does not validate downstream ranking criteria"
)

values = [5, 2, 8, 1, 3, 2]
output = insertion_sort(values)

print(spec)
print("output:", output)
print("sorted:", is_sorted(output))
print("same multiset:", same_multiset(values, output))

R: Complexity and Proof-Obligation Table

n <- 1:20

complexity_table <- data.frame(
  n = n,
  log_n = log2(n),
  linear = n,
  n_log_n = n * log2(n),
  quadratic = n^2,
  exponential = 2^n,
  interpretation = "complexity analysis compares growth patterns rather than one-machine timings"
)

proof_obligations <- data.frame(
  algorithm = c("insertion sort", "binary search", "breadth-first search"),
  precondition = c(
    "finite comparable list",
    "sorted finite sequence",
    "graph and valid start vertex"
  ),
  invariant = c(
    "processed prefix is sorted",
    "target remains in active interval if present",
    "queue processes vertices by distance layers"
  ),
  proof_method = c(
    "loop invariant",
    "interval invariant",
    "induction on graph distance"
  )
)

print(complexity_table)
print(proof_obligations)

Julia: Termination and Recurrence Cost

function binary_search(values, target)
    low = firstindex(values)
    high = lastindex(values)

    while low <= high
        mid = low + (high - low) ÷ 2

        if values[mid] == target
            return mid
        elseif values[mid] < target
            low = mid + 1
        else
            high = mid - 1
        end
    end

    return nothing
end

function merge_sort_cost(n)
    n <= 1 && return 1
    return 2 * merge_sort_cost(n ÷ 2) + n
end

values = [1, 2, 3, 5, 8, 13, 21]

println("binary search for 8: ", binary_search(values, 8))
println("merge-sort recurrence costs:")
for n in [1, 2, 4, 8, 16, 32, 64]
    println((n=n, cost=merge_sort_cost(n)))
end

Haskell: Typed Specifications, Results, and Proof Metadata

{-# OPTIONS_GHC -Wall #-}

data Complexity
  = Constant
  | Logarithmic
  | Linear
  | NLogN
  | Quadratic
  | Exponential
  deriving (Eq, Show)

data ProofMethod
  = LoopInvariant
  | Induction
  | StructuralInduction
  | GreedyInvariant
  | CaseAnalysis
  deriving (Eq, Show)

data AlgorithmSpec = AlgorithmSpec
  { algorithmName :: String
  , precondition :: String
  , postcondition :: String
  , invariant :: String
  , proofMethod :: ProofMethod
  , complexity :: Complexity
  } deriving (Eq, Show)

data Result a e
  = Success a
  | Failure e
  deriving (Eq, Show)

isSorted :: Ord a => [a] -> Bool
isSorted [] = True
isSorted [_] = True
isSorted (x:y:rest) = x <= y && isSorted (y:rest)

binarySearchSpec :: AlgorithmSpec
binarySearchSpec =
  AlgorithmSpec
    { algorithmName = "binary search"
    , precondition = "input sequence is sorted"
    , postcondition = "returns target position or missing result"
    , invariant = "target, if present, remains in active interval"
    , proofMethod = LoopInvariant
    , complexity = Logarithmic
    }

safeHead :: [a] -> Result a String
safeHead [] = Failure "empty list has no head"
safeHead (x:_) = Success x

main :: IO ()
main = do
  print binarySearchSpec
  print (isSorted [1, 2, 3, 5, 8])
  print (safeHead ([] :: [Int]))
  print (safeHead [10, 20, 30])

SQL: Algorithm, Proof, and Formal Reasoning Metadata

CREATE TABLE algorithm_specification (
  algorithm_id TEXT PRIMARY KEY,
  name TEXT NOT NULL,
  input_domain TEXT NOT NULL,
  output_specification TEXT NOT NULL,
  precondition TEXT NOT NULL,
  postcondition TEXT NOT NULL,
  complexity_note TEXT NOT NULL,
  responsible_use_note TEXT NOT NULL
);

CREATE TABLE proof_obligation (
  proof_id TEXT PRIMARY KEY,
  algorithm_id TEXT NOT NULL,
  proof_type TEXT NOT NULL,
  claim TEXT NOT NULL,
  invariant_or_measure TEXT NOT NULL,
  proof_status TEXT NOT NULL,
  risk_note TEXT NOT NULL,
  FOREIGN KEY (algorithm_id) REFERENCES algorithm_specification(algorithm_id)
);

CREATE TABLE termination_argument (
  termination_id TEXT PRIMARY KEY,
  algorithm_id TEXT NOT NULL,
  decreasing_measure TEXT NOT NULL,
  lower_bound TEXT NOT NULL,
  termination_claim TEXT NOT NULL,
  FOREIGN KEY (algorithm_id) REFERENCES algorithm_specification(algorithm_id)
);

CREATE TABLE formal_reasoning_warning (
  warning_id TEXT PRIMARY KEY,
  algorithm_id TEXT NOT NULL,
  warning TEXT NOT NULL,
  mitigation TEXT NOT NULL,
  FOREIGN KEY (algorithm_id) REFERENCES algorithm_specification(algorithm_id)
);

These examples treat algorithmic reasoning as structured, auditable metadata. Specifications can be recorded, invariants can be named, proof obligations can be tracked, termination measures can be documented, and responsible-use warnings can be attached to formally correct procedures.

Back to top ↑

GitHub Repository

The companion repository for this article is designed as a reproducible mathematical-thinking workspace focused on algorithm specifications, proof obligations, loop invariants, induction, termination arguments, complexity analysis, graph-algorithm assumptions, data-structure invariants, Haskell algebraic data types, SQL proof schemas, and responsible interpretation of formally correct computational systems.

Back to top ↑

Formal Correctness and Responsible Computing

Formal correctness is powerful, but it is not the same as ethical correctness. An algorithm can satisfy its specification and still produce harmful outcomes if the specification is unjust, incomplete, or detached from context. A ranking system can sort correctly while ranking by the wrong criterion. A classifier can optimize accuracy while harming a vulnerable group. A shortest-path algorithm can minimize travel time while ignoring safety, accessibility, or environmental cost.

Formal reasoning clarifies what the system does. Responsible reasoning asks whether the formal objective is legitimate, whether the inputs are fair, whether the categories are appropriate, whether the consequences are acceptable, and whether affected people have recourse.

Mathematical rigor is essential because it exposes assumptions. But once assumptions are exposed, they must be judged. Formal reasoning should make responsibility more visible, not hide it behind technical certainty.

Back to top ↑

Why Algorithms, Proof, and Formal Reasoning Matter

Algorithms, proof, and formal reasoning matter because modern systems increasingly depend on procedures that are too complex to trust by intuition alone. Algorithms sort, search, classify, recommend, allocate, route, schedule, authenticate, encrypt, optimize, detect, and decide. Their behavior affects infrastructure, medicine, finance, education, science, communication, public services, and everyday life.

Formal reasoning provides a way to inspect these systems. It asks what has been specified, what has been proven, what assumptions are required, what resources are needed, and what remains outside the proof. It distinguishes execution from correctness, correctness from usefulness, usefulness from justice, and formal guarantees from real-world consequences.

For mathematical thinking, algorithms offer a powerful lesson: a procedure is not understood merely because it can be run. It is understood when its specification, invariants, termination, correctness, complexity, and interpretation are clear.

The deeper purpose of formal reasoning is not to make computation abstract for its own sake. It is to make computational power accountable to reason. Algorithms should not be black boxes of procedural authority. They should be objects that can be specified, questioned, proven, tested, audited, improved, and interpreted responsibly.

Back to top ↑

Related Articles

• What Is Mathematical Thinking? Pattern, Proof, Architecture, and Reason
• Mathematical Thinking for Computer Science
• Recursion and Recursive Thinking
• Graphs, Networks, and Discrete Structure
• Discrete Mathematics and the Logic of Structure
• Combinatorics and the Mathematics of Possibility
• Sets, Relations, and Functions as Modes of Thought
• Logic and the Structure of Formal Inference
• Proof and the Logic of Mathematical Justification
• Mathematical Thinking and Proof Assistants

Further Reading

• Abelson, H., Sussman, G.J. and Sussman, J. (1996) Structure and Interpretation of Computer Programs. 2nd edn. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262510875/structure-and-interpretation-of-computer-programs/
• Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
• Dijkstra, E.W. (1976) A Discipline of Programming. Englewood Cliffs, NJ: Prentice-Hall.
• Gries, D. (1981) The Science of Programming. New York: Springer.
• Hoare, C.A.R. (1969) ‘An axiomatic basis for computer programming’, Communications of the ACM, 12(10), pp. 576–580. Available at: https://dl.acm.org/doi/10.1145/363235.363259
• Kleinberg, J. and Tardos, É. (2006) Algorithm Design. Boston: Pearson.
• Pierce, B.C. (2002) Types and Programming Languages. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262162098/types-and-programming-languages/
• Winskel, G. (1993) The Formal Semantics of Programming Languages. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262731034/the-formal-semantics-of-programming-languages/

Back to top ↑

References

• Abelson, H., Sussman, G.J. and Sussman, J. (1996) Structure and Interpretation of Computer Programs. 2nd edn. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262510875/structure-and-interpretation-of-computer-programs/
• Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
• Dijkstra, E.W. (1976) A Discipline of Programming. Englewood Cliffs, NJ: Prentice-Hall.
• Gries, D. (1981) The Science of Programming. New York: Springer.
• Hoare, C.A.R. (1969) ‘An axiomatic basis for computer programming’, Communications of the ACM, 12(10), pp. 576–580. Available at: https://dl.acm.org/doi/10.1145/363235.363259
• Kleinberg, J. and Tardos, É. (2006) Algorithm Design. Boston: Pearson.
• Knuth, D.E. (1997) The Art of Computer Programming, Volume 1: Fundamental Algorithms. 3rd edn. Boston: Addison-Wesley.
• Pierce, B.C. (2002) Types and Programming Languages. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262162098/types-and-programming-languages/
• Winskel, G. (1993) The Formal Semantics of Programming Languages. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262731034/the-formal-semantics-of-programming-languages/

Back to top ↑