Algorithm Cookbook
A practical cookbook of algorithmic patterns, correctness arguments, and implementation techniques.
83 notes
A practical cookbook of algorithmic patterns, correctness arguments, and implementation techniques.
Logic programming, type systems, verification, model checking, and program synthesis.
Logic programming, type systems, verification, model checking, and program synthesis.
Grammars, syntax, automata theory, regular and context free languages, parsing, recognition, and applications in compilers.
This section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms.
Linked list algorithms are dominated by pointer traversal and constant-time link updates.
Pointer code should be tested by checking structure, not only values.
Edge cases are inputs that sit near the boundary of an algorithm's assumptions.
An LRU cache stores a fixed number of key-value entries and removes the least recently used entry when capacity is exceeded.
A queue is a first-in, first-out structure.
A stack is a last-in, first-out (LIFO) structure.
An iterator is an object or procedure that visits the nodes of a linked list one at a time.
Memory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node.
An intrusive list stores the linkage fields inside the objects being linked.
A skip list augments a sorted linked list with multiple levels of forward pointers.
A persistent list is a list that preserves older versions after an update.
Pointer aliasing occurs when two or more references point to the same node.
A dummy head is a fixed node placed before the real head of a singly linked list.
Insertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes.
Deletion removes one or more nodes from a linked list by changing links around them.
Merging is a family of constructions that combine multiple linked lists into one or more output lists while preserving structural invariants.
Splitting a linked list means cutting one list into two or more lists while preserving the original nodes.
Merging combines two sorted singly linked lists into one sorted list by relinking nodes.
Fast and slow pointers are two references that traverse the same linked structure at different speeds.
A cycle exists in a linked list when some node’s `next` pointer eventually leads back to a previously visited node.
Reversal transforms a linked list so that the direction of all edges is flipped.
A sentinel node is an artificial node placed at the boundary of a linked list.
A doubly linked list is a sequence of nodes where each node stores a value, a reference to the next node, and a reference to the previous node.
A singly linked list is a sequence of nodes where each node stores a value and a reference to the next node.
Linked lists are the first data structure in this book where the shape of the data matters as much as the values stored inside it.
Boundary conditions define the valid domain of indices, ranges, and states in an algorithm.
Array and string problems often look different on the surface, but many reduce to a small number of reusable patterns.
Flood fill explores a connected region in a grid starting from a seed cell and marks or transforms all cells that belong to the same region.
Spiral traversal visits a matrix layer by layer, moving right across the top row, down the right column, left across the bottom row, and up the left column,...
Matrix traversal processes a two-dimensional array in a defined order.
A trie is a tree structure for storing a set of strings so that common prefixes are shared.
Parsing expressions converts a sequence of tokens into a structured form that reflects operator precedence and associativity.
String comparison determines the ordering or equality of two strings.
Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly.
Run-Length Encoding (RLE) compresses sequences by replacing consecutive equal values with a pair `(value, count)`.
A frequency table records how many times each value appears in an array, string, or stream.
Anagrams are strings or sequences that contain the same elements with the same multiplicities, possibly in different order.
A palindrome is a sequence that reads the same forward and backward.
Substring search locates occurrences of a pattern `p` inside a text `s`.
Tokenization converts a string into a sequence of meaningful units called tokens.
String scanning is the basic operation behind parsing, tokenization, validation, search, and text normalization.
Deduplication removes repeated values while preserving a chosen notion of identity and, optionally, order.
In-place modification changes an array without allocating another array of the same size.
Array rotation moves elements by a fixed offset while preserving their relative circular order.
Partitioning rearranges an array so that elements are grouped by a predicate.
Sliding windows maintain a contiguous subarray `[l, r)` while both endpoints move forward.
The two pointers technique uses two indices that move through an array or string in a controlled way.
A difference array is the inverse pattern of a prefix sum.
Prefix sums are a preprocessing technique for answering repeated range sum queries on an array.
Array traversal is the base operation for all algorithms over linear data.
This chapter studies linear data as the primary substrate for algorithm design.
Even when the algorithmic idea is correct, implementations fail in predictable ways.
Benchmarking measures how an implementation behaves on real inputs and real hardware.
Stability and determinism describe how predictably an algorithm behaves when there are ties, repeated values, or multiple valid answers.
Algorithms are usually described with mathematical integers and real numbers.
Data representation is the choice of concrete form used to store the objects in a problem.
Implementation discipline means translating an algorithm into code without changing its meaning accidentally.
Pseudocode is a bridge between the problem statement and an implementation.
A reduction transforms one problem into another problem.
Amortized analysis studies the average cost of operations over a sequence, even when individual operations are sometimes expensive.
Randomized algorithms use random choices during execution.
Dynamic programming solves problems by storing answers to subproblems and reusing them.
Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers.
A greedy algorithm builds a solution by making one locally best choice at a time.
A brute force baseline is the simplest correct algorithm you can write from the problem statement.
Testing does not prove an algorithm correct, but it exposes mistakes in specifications, invariants, edge cases, and implementation details.
Edge cases are valid inputs that sit at the boundary of the specification.
A lower bound states that every algorithm for a problem must perform at least a certain amount of work in some model of computation.
Big O notation provides a formal way to describe how a function grows.
Space complexity measures how much memory an algorithm uses as a function of input size.
Time complexity describes how the running time of an algorithm grows as the input size grows.
Recursive algorithms replace loop structure with self-reference.
Loop invariants are the primary tool for reasoning about iterative algorithms.
A correctness argument explains why an algorithm returns an acceptable output for every valid input.
An algorithm does not operate on an abstract idea of data.
An algorithm begins with a precise statement of the problem.
This chapter defines how you think about algorithms before you write any code.
This volume studies theoretical and practical foundations of computation.