Introduction to Algorithms and Data Structures

When a novice programmer writes a `for` loop to find the largest number in a list, the code works; when that same programmer is asked to design a system that serves one billion search queries per day, the same instinct—linear, sequential, brute-force thinking—collapses under its own weight. The transition from scripting to engineering is, at its heart, a transition from *making things work* to *making things work at scale, with guarantees*. This transition requires two complementary competencies: the ability to articulate computational procedures as algorithms with predictable behavior, and the ability to organize information into data structures that make those procedures efficient. This chapter is dedicated to making those two competencies explicit, defining them rigorously, and demonstrating why their interplay constitutes the bedrock of computer science as a discipline.

Defining Algorithms with Precision

The word algorithm derives from the name of the ninth-century Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī, whose treatise *Kitāb al-Jabr wa al-Muqābala* gave algebra both its name and many of its foundational procedures. Today the term refers to something more specific: a finite, well-defined sequence of instructions that transforms input into output. Several authorities have formalized this intuition. Donald Knuth, in *The Art of Computer Programming*, defines an algorithm as a finite set of rules that gives a sequence of operations for solving a specific class of problems, requiring five essential properties: finiteness, definiteness, input, output, and effectiveness. Each of these properties deserves close examination because the difference between a correct algorithm and an incorrect one frequently lies in whether one of them has been violated.

Finiteness means that the algorithm must terminate after a bounded number of steps. This property distinguishes an algorithm from a *process*: a process may run forever (such as the event loop of an operating system), but an algorithm must, in principle, produce its answer and stop. A procedure that increments a counter and never returns a value is not, in Knuth's sense, an algorithm—it is an infinite loop. Finiteness is what allows us to speak of an algorithm's *running time*, which is meaningless if the procedure never halts. The famous Halting Problem, proved undecidable by Alan Turing in 1936, demonstrates that no general algorithm can determine whether an arbitrary program will halt; yet every individual algorithm we design is, by definition, required to halt on every input.

Definiteness requires that each step of the algorithm be precise and unambiguous. A recipe that says "bake until it looks right" fails this test; an algorithm must specify, for every possible situation, exactly what to do next. This is why programming languages are formal systems with rigid syntax: they exist to eliminate ambiguity in the description of computational steps. When we express an algorithm in pseudocode, we are translating its mathematical specification into a form that is definite enough to be executed.

Input specifies what is given to the algorithm before it begins. An algorithm may have zero inputs (such as one that outputs the digits of π), one input, or many inputs. The set of inputs is precisely defined and constitutes the *domain* of the algorithm. Output is the result produced by the algorithm after termination. An algorithm must produce at least one output, because otherwise there is no way to verify that it accomplished its purpose. The pairing of input and output is what makes algorithms *functions* in the mathematical sense: each input is mapped to a specific output.

Effectiveness means that every operation in the algorithm must be primitive enough to be carried out, in principle, by a person using only paper and pencil in a finite amount of time. Operations like "divide $a$ by $b$" or "compare two integers" are effective; operations like "find the true meaning of the universe" are not, because no finite procedure can verify that the answer has been found. This property connects algorithms to the physical reality of computation: they must be implementable on real machines.

To illustrate these properties working in concert, consider the classical algorithm for computing the greatest common divisor of two positive integers, attributed to Euclid around 300 BCE and reproduced in his *Elements* (Book VII, Proposition 2). In modern notation:

``` EuclideanGCD(a, b): while b ≠ 0: t ← a mod b a ← b b ← t return a ```

This procedure satisfies all five properties. It terminates because the second argument strictly decreases with each iteration and is bounded below by zero (finiteness). Each step is unambiguous and executable (definiteness). It accepts two positive integers as input and produces a single positive integer as output (input, output). The `mod` operation and the assignment are basic operations a person can carry out by hand (effectiveness). The algorithm is correct because it relies on the invariant that $\gcd(a, b) = \gcd(b, a \bmod b)$, a theorem that has been verified over more than two millennia.

It is worth pausing to distinguish an algorithm from a program. An algorithm is an abstract, mathematical object—a method for solving a class of problems. A program is a concrete realization of that method in a particular programming language, running on a particular machine, with particular performance characteristics. The Euclidean algorithm written in pseudocode is portable across all languages and machines; an implementation of that algorithm in Python running on a laptop is one specific program among infinitely many possible programs that all implement the same algorithm. This distinction matters because programmers often conflate the two and attribute performance problems to the algorithm when, in fact, the algorithm is sound and only the implementation is suboptimal. Conversely, a beautiful algorithm poorly implemented can perform worse than a mediocre algorithm with an excellent implementation. Throughout this book, we will analyze algorithms at the abstract level while keeping one foot planted in the realities of implementation.

A related distinction separates an algorithm from a heuristic. A heuristic is a problem-solving strategy that is not guaranteed to produce an optimal or even a correct solution, but that is useful in practice because it is fast or simple. For example, the nearest-neighbor heuristic for the Traveling Salesman Problem produces a route that is generally good but can be arbitrarily far from optimal. Algorithms, in the strict sense, are procedures that are provably correct on every valid input; heuristics are educated guesses. The distinction blurs in fields such as machine learning and optimization, where "algorithms" sometimes refer to iterative procedures with convergence guarantees rather than finite-step correctness proofs. For the purposes of this book, we will use the classical definition.

Defining Data Structures: Organization as the Foundation of Computation

If algorithms describe *what to do*, data structures describe *what to do it to*. A data structure is a specialized format for organizing, storing, and managing data so that it can be accessed and modified efficiently. The choice of data structure is rarely an afterthought; it is often the single most consequential design decision in a software system. A poorly chosen structure can make an otherwise elegant algorithm crawl; a well-chosen structure can make a naive algorithm fly.

To analyze data structures rigorously, computer scientists separate them into two layers: the logical (or abstract) layer and the physical (or storage) layer. The logical layer describes what operations the structure supports and what guarantees it provides—what we typically call an **Ab