foundations | brain

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.25 Common Failure Modes

Even when the algorithmic idea is correct, implementations fail in predictable ways. These failures are not random. They arise from mismatches between the specification, the model, and the code. Recognizing these patterns early reduces debugging time and prevents subtle errors. Problem You have an implementation that behaves incorrectly or inconsistently, and you need a systematic way to identify likely causes. Solution Check the implementation against a small set of known...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.23 Stability and Determinism

Stability and determinism describe how predictably an algorithm behaves when there are ties, repeated values, or multiple valid answers. These properties do not always change the mathematical objective, but they often change the required output, the implementation, and the tests. An algorithm is deterministic if the same input always produces the same output. An algorithm is stable, in the common sorting sense, if equal keys keep their original relative order....

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.24 Benchmarking

Benchmarking measures how an implementation behaves on real inputs and real hardware. Complexity analysis tells you how an algorithm should scale. Benchmarking tells you what the constants, memory effects, and implementation details actually do. A benchmark should answer a specific question. It should not merely produce a number. Useful questions include whether one implementation is faster than another, whether the running time grows as expected, whether memory usage fits the...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.22 Numerical Limits

Algorithms are usually described with mathematical integers and real numbers. Implementations run with finite machine values. This difference matters. An algorithm can be correct in theory and still fail in code because an integer overflows, a floating-point comparison is unstable, or a counter cannot represent the true answer. Numerical limits should be checked during design, not after debugging. The input constraints often tell you which numeric type is required. Problem...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.21 Data Representation

Data representation is the choice of concrete form used to store the objects in a problem. The same mathematical object can have many representations, and each representation makes some operations cheap while making others expensive. Choosing the representation is therefore part of algorithm design. A graph can be stored as an edge list, adjacency list, adjacency matrix, or compressed sparse structure. A set can be stored as a sorted array,...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

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...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.18 Reductions

A reduction transforms one problem into another problem. It is a way to reuse algorithms and transfer difficulty. If problem A can be converted into problem B, and we already know how to solve B, then we can solve A by translating the input, running the solver for B, and translating the output back. Reductions are useful in two directions. For algorithm design, they let you solve a new problem...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.16 Randomization

Randomized algorithms use random choices during execution. The output or running time may depend on those choices. Randomization is useful when it simplifies design, avoids adversarial patterns, or gives good expected performance with a small amount of code. A randomized algorithm still needs a correctness contract. The contract must say whether the algorithm is always correct, probably correct, or correct in expectation. Problem You want to use randomness to make...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.15 Dynamic Programming

Dynamic programming solves problems by storing answers to subproblems and reusing them. It is useful when a naive recursive solution repeats the same work many times. Instead of recomputing a subproblem every time it appears, the algorithm computes it once and records the result. The method depends on two properties: Optimal substructure: The answer to a larger problem can be built from answers to smaller problems. Overlapping subproblems: The same...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.17 Amortized Analysis

Amortized analysis studies the average cost of operations over a sequence, even when individual operations are sometimes expensive. It is used when a data structure has rare costly steps that are paid for by many cheap steps. The guarantee is different from average-case analysis. Amortized analysis does not require random input or a probability distribution. It gives a worst-case bound over any valid sequence of operations. Problem You have an...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

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...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.14 Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers. It is useful when the original problem has repeated structure and when the cost of combining subanswers is controlled. The pattern has three parts: divide: split the input into smaller pieces conquer: solve each piece recursively combine: merge the subanswers into the answer for the full input The key question is...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.12 Brute Force Baselines

A brute force baseline is the simplest correct algorithm you can write from the problem statement. It may be too slow for the final constraints, but it is valuable because it gives you a reference answer, exposes edge cases, and clarifies what the optimized algorithm must preserve. A good baseline is intentionally direct. It should follow the definition of the problem more closely than the efficient solution does. This makes...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.11 Testing Algorithms

Testing does not prove an algorithm correct, but it exposes mistakes in specifications, invariants, edge cases, and implementation details. A good test suite is built from the problem statement. It checks whether the implementation satisfies the input and output contract under ordinary, boundary, and adversarial conditions. Algorithm tests should not only ask, "Does this example pass?" They should ask, "What assumption would fail if this test failed?" Each test should...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.13 Greedy Choices

A greedy algorithm builds a solution by making one locally best choice at a time. It does not reconsider earlier choices. This makes greedy algorithms simple and fast, but also easy to get wrong. The main difficulty is proof: you must show that each local choice can be part of some globally optimal solution. Greedy algorithms work when the problem has structure that makes local progress safe. A choice is...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.10 Edge Cases

Edge cases are valid inputs that sit at the boundary of the specification. They are often small, empty, repeated, extreme, or structurally degenerate. They matter because many algorithms are designed around the typical case, while many bugs occur at the boundary. An edge case should not be treated as an exception to the problem. It is part of the problem. If the input is allowed by the specification, the algorithm...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.9 Lower Bounds

A lower bound states that every algorithm for a problem must perform at least a certain amount of work in some model of computation. It tells you what cannot be improved. Upper bounds come from algorithms. Lower bounds come from arguments about necessity. For example, if an algorithm scans an unsorted array to find the maximum value, the linear-time algorithm gives an upper bound of $O(n)$. A lower bound proves...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.7 Space Complexity

Space complexity measures how much memory an algorithm uses as a function of input size. It complements time complexity and often determines whether an algorithm is feasible in practice. Memory includes both the input representation and any additional storage used during execution. The focus in algorithm design is usually on auxiliary space , which is the extra memory beyond the input itself. Problem You have an algorithm and need to...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.8 Big O Notation

Big O notation provides a formal way to describe how a function grows. In algorithms, it is used to express upper bounds on time and space complexity. The notation suppresses constant factors and lower order terms so that the dominant growth rate is clear. Problem You have derived a function that counts operations, such as (3n^2 + 5n + 7), and you need a standard way to express its growth....

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.5 Recursion Invariants

Recursive algorithms replace loop structure with self-reference. Instead of tracking progress through iteration, you track progress through problem size. A recursion invariant describes what each call is responsible for computing and how that responsibility relates to smaller subproblems. The core idea is simple: every recursive call must solve a strictly smaller instance of the same problem, and the combination of those solutions must produce a correct result for the original...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.6 Time Complexity

Time complexity describes how the running time of an algorithm grows as the input size grows. It does not try to predict the exact number of seconds on a particular machine. Instead, it gives a portable way to compare algorithms by counting how many primitive operations they perform as a function of the input. The main size parameter is usually written as (n). For graphs, we often use two parameters:...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.3 Correctness Arguments

A correctness argument explains why an algorithm returns an acceptable output for every valid input. It should be written before, or at least alongside, the implementation. Code tells you what the algorithm does. A correctness argument tells you why those steps solve the stated problem. A good correctness argument is local. It does not rely on intuition about the whole program at once. Instead, it identifies a property that remains...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.4 Loop Invariants

Loop invariants are the primary tool for reasoning about iterative algorithms. They formalize what remains true at each step of a loop and provide a bridge between local updates and global correctness. A loop invariant is not an observation after the fact. It is a design component that guides how the loop is written. Problem You need a reliable method to prove that a loop-based algorithm is correct, especially when...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.2 Input and Output Models

An algorithm does not operate on an abstract idea of data. It operates on a chosen model of data. The same problem can look easy or hard depending on how the input is represented and how the output must be produced. For this reason, every serious algorithm description should state not only what the input means, but also how the input is presented to the algorithm. The input model defines...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.1 Problem Statements

An algorithm begins with a precise statement of the problem. The goal is to define the task so clearly that both correctness and complexity follow from the definition. Ambiguity at this stage propagates into proofs, implementations, and tests. A problem statement consists of four parts: input, output, constraints, and guarantees. Input specifies the structure and domain of data. You describe types, sizes, ordering, and any preconditions. For example, an input...

Programming › Algorithm Cookbook ›

Chapter 1. Foundations

This chapter defines how you think about algorithms before you write any code. It establishes a small set of rules for describing problems, reasoning about correctness, and estimating cost. Every later technique relies on these rules, so the focus here stays on precision and repeatability. An algorithm begins with a contract. You specify inputs, outputs, and constraints in a way that removes ambiguity. This includes data shape, value ranges, ordering...

Maths › 03. Logic and Foundations ›

24. Limits of Formal Systems

Limits of formal systems study the boundaries of what can be proved, computed, and expressed within precise mathematical frameworks, and they show that even very strong systems have inherent restrictions that cannot be removed by technical refinement alone. The chapter begins with incompleteness, where certain true statements cannot be derived from a given formal system, provided that the system is sufficiently expressive and consistent, and this reveals a gap between...

Maths › 03. Logic and Foundations ›

22. Foundations Programs

Foundations programs study different ways of explaining the nature, meaning, and justification of mathematics, and they ask what mathematics is about, what counts as a proof, and how mathematical knowledge should be organized. The chapter begins with logicism, which attempts to reduce mathematics to logic by showing that mathematical concepts and theorems can be derived from purely logical principles. Formalism is then introduced as the view that mathematics can be...

Maths › 03. Logic and Foundations ›

22. Foundations Programs

Foundations programs study different ways of explaining the nature, meaning, and justification of mathematics, and they ask what mathematics is about, what counts as a proof, and how mathematical knowledge should be organized. The chapter begins with logicism, which attempts to reduce mathematics to logic by showing that mathematical concepts and theorems can be derived from purely logical principles. Formalism is then introduced as the view that mathematics can be...

Maths › 03. Logic and Foundations ›

14.5 Extensions

14.5 Extensions and Refinements Gödel’s original theorems admit stronger forms and alternative formulations. These refinements clarify exactly which assumptions are needed and how incompleteness behaves across different systems. Rosser’s Improvement Gödel’s first theorem used a strengthened consistency assumption. Rosser showed that this can be weakened. Instead of the original Gödel sentence, Rosser constructs a sentence $R$ that balances proofs of a statement and its negation. Informally, $R$ says: “if there...

Maths › 03. Logic and Foundations ›

14.4 Implications

14.4 Implications for Formal Systems Gödel’s theorems change how we understand formal systems. They do not weaken logic. They clarify its limits and force a more precise view of what formal reasoning can achieve. Separation of Truth and Provability Before Gödel, it was natural to expect that every true mathematical statement could be proved. The incompleteness theorem shows this expectation fails for sufficiently strong systems. There exist sentences $A$ such...

Maths › 03. Logic and Foundations ›

14.1 Arithmetization

14.1 Arithmetization of Syntax Gödel’s key idea is that syntax can be represented inside arithmetic. Symbols, formulas, and proofs are encoded as natural numbers. Once this is done, statements about formulas become statements about numbers, and a formal system can reason about its own expressions. Coding Symbols Start with a finite alphabet of symbols: $$ {0, S, +, \times, =, (, ), \forall, \exists, \neg, \land, \lor, \to, \dots} $$...

Maths › 03. Logic and Foundations ›

14.3 Second Incompleteness

14.3 Second Incompleteness Theorem The first incompleteness theorem shows that some true statements cannot be proved. The second goes further. It shows that a system strong enough to express arithmetic cannot prove its own consistency. Formalizing Consistency A system is consistent if it does not prove a contradiction. For example, it does not prove both $A$ and $¬A$. Using arithmetization, we express this inside arithmetic. Let: $$ \mathrm{Prov}(y) $$ mean...

Maths › 03. Logic and Foundations ›

13.4 Consistency Proofs

13.4 Consistency Proofs A formal system should avoid proving contradictions. Consistency is the property that a system does not collapse into proving everything. At the simplest level, a system is consistent if there is some formula $A$ such that the system does not prove both $A$ and $¬A$. More commonly, we say that a system is consistent if there is no formula $A$ such that: $$ \vdash A $$ and...

Maths › 03. Logic and Foundations ›

9.2 Large Cardinals

Large cardinal theory studies strong axioms asserting the existence of infinite cardinals with properties far beyond those provable in ZFC, and these axioms are important because they measure the strength of set theoretic principles and provide a systematic hierarchy of stronger and stronger extensions of ordinary set theory. The basic idea is that some cardinals are so large that the universe below them resembles the whole universe in certain structural...

Maths › 03. Logic and Foundations ›

2. First-Order Logic

First-order logic extends propositional logic by allowing formulas to speak about objects, properties of objects, and relations between objects, rather than treating every statement as an indivisible unit. The language contains variables, constants, function symbols, predicate symbols, logical connectives, and quantifiers, and these symbols allow mathematical statements to be expressed with much greater internal structure than in propositional logic. The first part of the chapter defines terms, predicates, and formulas,...

Maths › 03. Logic and Foundations ›

1. Propositional Logic

Propositional logic studies reasoning with statements that can be either true or false, and it provides a formal language together with precise rules that allow such reasoning to be carried out in a systematic and verifiable way, independent of the specific meaning of the statements involved. The basic objects of study are propositional variables, which serve as placeholders for statements, and these variables are combined using logical connectives to form...

Maths › 03. Logic and Foundations ›

Preface

Preface Mathematical logic studies the structure of reasoning with the same precision that algebra studies equations or topology studies space. It provides formal languages, semantic frameworks, and proof systems that let you state claims unambiguously, analyze their meaning, and verify their correctness. This book develops those components in a unified way, with an emphasis on how syntax, semantics, and computation interact. You will begin with propositional and first-order logic. The...