Algorithm Cookbook
A practical cookbook of algorithmic patterns, correctness arguments, and implementation techniques.
Tag
Computer Science
83 notes
Chapter 20. Logic in Programming
Logic programming, type systems, verification, model checking, and program synthesis.
Chapter 20. Logic in Programming
Logic programming, type systems, verification, model checking, and program synthesis.
Chapter 19. Formal Languages
Grammars, syntax, automata theory, regular and context free languages, parsing, recognition, and applications in compilers.
3.25 Case Studies
This section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms.
3.24 Complexity Analysis
Linked list algorithms are dominated by pointer traversal and constant-time link updates.
3.23 Testing Pointer Code
Pointer code should be tested by checking structure, not only values.
3.22 Edge Cases
Edge cases are inputs that sit near the boundary of an algorithm's assumptions.
3.21 LRU Cache Structure
An LRU cache stores a fixed number of key-value entries and removes the least recently used entry when capacity is exceeded.
3.20 Queue via List
A queue is a first-in, first-out structure.
3.19 Stack via List
A stack is a last-in, first-out (LIFO) structure.
3.18 Iterators
An iterator is an object or procedure that visits the nodes of a linked list one at a time.
3.17 Memory Ownership
Memory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node.
3.16 Intrusive Lists
An intrusive list stores the linkage fields inside the objects being linked.
3.15 Skip Lists
A skip list augments a sorted linked list with multiple levels of forward pointers.
3.14 Persistent Lists
A persistent list is a list that preserves older versions after an update.
3.13 Pointer Aliasing
Pointer aliasing occurs when two or more references point to the same node.
3.12 Dummy Heads (Dummy Nodes)
A dummy head is a fixed node placed before the real head of a singly linked list.
3.11 Insertion Patterns
Insertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes.
3.10 Deletion Patterns
Deletion removes one or more nodes from a linked list by changing links around them.
3.9 Merge Patterns
Merging is a family of constructions that combine multiple linked lists into one or more output lists while preserving structural invariants.
3.8 Split Patterns
Splitting a linked list means cutting one list into two or more lists while preserving the original nodes.
3.7 Merge Two Sorted Lists
Merging combines two sorted singly linked lists into one sorted list by relinking nodes.
3.6 Fast and Slow Pointers
Fast and slow pointers are two references that traverse the same linked structure at different speeds.
3.5 Cycle Detection
A cycle exists in a linked list when some node’s `next` pointer eventually leads back to a previously visited node.
3.4 Reversal
Reversal transforms a linked list so that the direction of all edges is flipped.
3.3 Sentinel Nodes
A sentinel node is an artificial node placed at the boundary of a linked list.
3.2 Doubly Linked Lists
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.
3.1 Singly Linked Lists
A singly linked list is a sequence of nodes where each node stores a value and a reference to the next node.
Chapter 3. Linked Lists and Pointers
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.
2.25 Boundary Conditions
Boundary conditions define the valid domain of indices, ranges, and states in an algorithm.
2.24 Common Patterns
Array and string problems often look different on the surface, but many reduce to a small number of reusable patterns.
2.23 Flood Fill
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.
2.22 Spiral Traversal
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,...
2.21 Matrix Traversal
Matrix traversal processes a two-dimensional array in a defined order.
2.20 Tries
A trie is a tree structure for storing a set of strings so that common prefixes are shared.
2.19 Parsing Expressions
Parsing expressions converts a sequence of tokens into a structured form that reflects operator precedence and associativity.
2.18 String Comparison
String comparison determines the ordering or equality of two strings.
2.17 Rolling Hashes
Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly.
2.16 Run-Length Encoding
Run-Length Encoding (RLE) compresses sequences by replacing consecutive equal values with a pair `(value, count)`.
2.15 Frequency Tables
A frequency table records how many times each value appears in an array, string, or stream.
2.14 Anagrams
Anagrams are strings or sequences that contain the same elements with the same multiplicities, possibly in different order.
2.13 Palindromes
A palindrome is a sequence that reads the same forward and backward.
2.12 Substring Search
Substring search locates occurrences of a pattern `p` inside a text `s`.
2.11 Tokenization
Tokenization converts a string into a sequence of meaningful units called tokens.
2.10 String Scanning
String scanning is the basic operation behind parsing, tokenization, validation, search, and text normalization.
2.9 Deduplication
Deduplication removes repeated values while preserving a chosen notion of identity and, optionally, order.
2.8 In-Place Modification
In-place modification changes an array without allocating another array of the same size.
2.7 Rotation
Array rotation moves elements by a fixed offset while preserving their relative circular order.
2.6 Partitioning
Partitioning rearranges an array so that elements are grouped by a predicate.
2.5 Sliding Windows
Sliding windows maintain a contiguous subarray `[l, r)` while both endpoints move forward.
2.4 Two Pointers
The two pointers technique uses two indices that move through an array or string in a controlled way.
2.3 Difference Arrays
A difference array is the inverse pattern of a prefix sum.
2.2 Prefix Sums
Prefix sums are a preprocessing technique for answering repeated range sum queries on an array.
2.1 Array Traversal
Array traversal is the base operation for all algorithms over linear data.
Chapter 2. Arrays and Strings
This chapter studies linear data as the primary substrate for algorithm design.
1.25 Common Failure Modes
Even when the algorithmic idea is correct, implementations fail in predictable ways.
1.24 Benchmarking
Benchmarking measures how an implementation behaves on real inputs and real hardware.
1.23 Stability and Determinism
Stability and determinism describe how predictably an algorithm behaves when there are ties, repeated values, or multiple valid answers.
1.22 Numerical Limits
Algorithms are usually described with mathematical integers and real numbers.
1.21 Data Representation
Data representation is the choice of concrete form used to store the objects in a problem.
1.20 Implementation Discipline
Implementation discipline means translating an algorithm into code without changing its meaning accidentally.
1.19 Pseudocode Style
Pseudocode is a bridge between the problem statement and an implementation.
1.18 Reductions
A reduction transforms one problem into another problem.
1.17 Amortized Analysis
Amortized analysis studies the average cost of operations over a sequence, even when individual operations are sometimes expensive.
1.16 Randomization
Randomized algorithms use random choices during execution.
1.15 Dynamic Programming
Dynamic programming solves problems by storing answers to subproblems and reusing them.
1.14 Divide and Conquer
Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers.
1.13 Greedy Choices
A greedy algorithm builds a solution by making one locally best choice at a time.
1.12 Brute Force Baselines
A brute force baseline is the simplest correct algorithm you can write from the problem statement.
1.11 Testing Algorithms
Testing does not prove an algorithm correct, but it exposes mistakes in specifications, invariants, edge cases, and implementation details.
1.10 Edge Cases
Edge cases are valid inputs that sit at the boundary of the specification.
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.
1.8 Big O Notation
Big O notation provides a formal way to describe how a function grows.
1.7 Space Complexity
Space complexity measures how much memory an algorithm uses as a function of input size.
1.6 Time Complexity
Time complexity describes how the running time of an algorithm grows as the input size grows.
1.5 Recursion Invariants
Recursive algorithms replace loop structure with self-reference.
1.4 Loop Invariants
Loop invariants are the primary tool for reasoning about iterative algorithms.
1.3 Correctness Arguments
A correctness argument explains why an algorithm returns an acceptable output for every valid input.
1.2 Input and Output Models
An algorithm does not operate on an abstract idea of data.
1.1 Problem Statements
An algorithm begins with a precise statement of the problem.
Chapter 1. Foundations
This chapter defines how you think about algorithms before you write any code.
68. Computer Science
This volume studies theoretical and practical foundations of computation.