What you will learn in Algorithms Every Programmer Should Know
Chapter by chapter
Chapter 1: The Language of Algorithms
This introduction explains why algorithms matter in everyday software and why choosing one requires practical judgment, not just a search for theoretical optimality.
What you learn in chapter 1 →Chapter 2: Gale-Shapley Algorithm
The introduction frames Gale-Shapley as a way to match two equal-sized groups by preference without leaving a mutually preferred unmatched pair, and introduces deferred acceptance and proposer bias.
What you learn in chapter 2 →Chapter 3: Hungarian Algorithm
Introduces the Hungarian algorithm’s assignment objective, the balanced cost matrix, and the stated complexity improvement.
What you learn in chapter 3 →Chapter 4: Rabin–Karp Algorithm
Introduces Rabin–Karp as a hash-based way to search for a pattern in text, and explains how rolling hashes and collisions affect its performance.
What you learn in chapter 4 →Chapter 5: Knuth-Morris-Pratt Algorithm
This introduction explains why naive string search wastes work on repetitive text and how KMP uses pattern information to avoid backtracking.
What you learn in chapter 5 →Chapter 6: Horspool’s Algorithm
Introduces Horspool’s right-to-left, mismatch-driven approach to string matching and explains why its precomputed shifts can speed up searches.
What you learn in chapter 6 →Chapter 7: Knapsack Algorithm
Introduces 0/1 Knapsack as choosing the highest-value subset under a limit, and explains why dynamic programming stores smaller solutions instead of repeating work.
What you learn in chapter 7 →Chapter 8: Ant Colony Optimization Algorithm
The introduction motivates a good-enough alternative to costly exact optimization and explains how ACO adapts ants’ pheromone-guided foraging to graph search.
What you learn in chapter 8 →Chapter 9: Floyd-Warshall Algorithm
Introduces Floyd-Warshall as a dynamic-programming approach to finding exact shortest distances between every pair of nodes in a dense graph.
What you learn in chapter 9 →Chapter 10: Push Relabel Algorithm
Introduces maximum network flow as a capacity problem and motivates Push-Relabel’s local approach over repeated global path searches.
What you learn in chapter 10 →Chapter 11: Bron-Kerbosch Algorithm
The introduction shifts from maximum flow to finding mutually connected groups in a graph and gives a high-level account of Bron–Kerbosch’s backtracking approach.
What you learn in chapter 11 →Chapter 12: A* Algorithm
The introduction frames A* as a way to find the cheapest route to a specific destination while using an estimate of the remaining distance to guide the search.
What you learn in chapter 12 →Concepts explained in this book
- dynamic programmingAn algorithm-design technique that solves overlapping subproblems and stores intermediate results to avoid repeated computation.
- space complexityA measure of how an algorithm's memory usage grows as a function of input size.
- time complexityA measure of how an algorithm's running time grows with input size.
- knapsack problemAn optimization problem that selects whole items to maximize total value without exceeding a capacity constraint.
- Bron–Kerbosch algorithmThe Bron–Kerbosch algorithm is a recursive backtracking algorithm for enumerating the maximal cliques of an undirected graph.
- ant colony optimizationA metaheuristic inspired by ant foraging in which artificial agents explore solutions and use simulated pheromone trails to reinforce promising choices.
- Knuth-Morris-Pratt algorithmThe Knuth-Morris-Pratt algorithm is a string-search procedure that uses pattern prefix-suffix information to avoid rechecking text characters after a mismatch.
- cliqueA clique is a set of vertices in a graph in which every pair of distinct vertices is connected by an edge.
- maximal clique problemA maximal clique is a clique that cannot be enlarged by adding another vertex while preserving pairwise adjacency.
- LPS arrayAn LPS array stores, for each pattern position, the length of the longest proper prefix that is also a suffix of the pattern prefix ending there.
- matrixA matrix is a rectangular array of values indexed by row and column.
- capacityCapacity is the maximum total resource amount that a selected collection of items may consume.
- greedy algorithmA greedy algorithm chooses a locally optimal option at each step without accounting for the effects of future choices.
- push-relabel algorithmThe push-relabel algorithm computes a maximum flow by maintaining a preflow and vertex height labels, then locally pushing excess flow and relabeling vertices.
- backtrackingSearch backtracking returns to an earlier search state after exploring one branch so that other branches can be examined.
- Boyer-Moore-Horspool algorithmThe Boyer-Moore-Horspool algorithm is a string-search procedure that compares pattern characters from right to left and uses character-based skip distances to shift the pattern.
- maximum flowThe problem of finding the greatest feasible flow from a source to a sink in a capacitated network.
- pheromoneA chemical signal deposited by ants that influences other ants’ route choices; in ant colony optimization, a digital analogue encodes route preference.
- algorithmAn algorithm is a finite step-by-step procedure that transforms specified inputs into a solution to a problem.
- overlapping subproblemAn overlapping subproblem is a smaller computational problem that occurs repeatedly within the recursive decomposition of a larger problem.
- linear time complexityAn asymptotic linear-time bound in an input of size N, also written O(m) when that input's size is denoted m.
- constant timeA time complexity, denoted O(1), that remains bounded independently of input size.
- push operationA flow push sends excess flow to a neighboring vertex with residual capacity whose height is exactly one unit lower.
- bad character shift tableA lookup table that maps characters to safe distances for shifting a pattern after a mismatch in string searching.
- A* algorithmA* is a best-first search algorithm that prioritizes paths using their cost so far and a heuristic estimate of the remaining cost.
- pivotingPivoting selects a pivot element to restrict branching and reduce redundant work during a search.
- recursionRecursion is a technique in which a function directly or indirectly invokes itself to solve progressively smaller or simpler instances of a problem.
- Floyd–WarshallThe Floyd-Warshall algorithm is a dynamic programming algorithm that computes shortest-path distances between every pair of vertices in a weighted graph.
- 0/1 constraintA 0/1 constraint restricts each item decision to either excluding the item or including it once.
- state transition formulaA recurrence that computes a problem state's value from values of other states.
- Hungarian algorithmThe Hungarian algorithm is a polynomial-time optimization procedure for finding a minimum-cost one-to-one assignment between two equally sized sets.
- preflowA preflow is a flow assignment that respects edge capacities and flow conservation at intermediate vertices may be temporarily violated by allowing excess flow.
- pheromone evaporationAn ant colony optimization operation that reduces pheromone weights across graph edges to weaken previously favored paths.
- excess flowExcess flow is the net amount of incoming flow currently retained at a vertex rather than sent onward.
- relabel operationA relabel operation raises an active vertex's height to enable a valid push along an edge with residual capacity.
- hash functionA hash function deterministically maps input data, such as a key, to an index or hash value.
- residual capacityResidual capacity is the additional flow that can be sent along an edge, accounting for its capacity and current flow.
- hash collisionA hash collision occurs when distinct keys produce the same hash index or hash value.
- Rabin-Karp algorithmThe Rabin-Karp algorithm is a string-search procedure that compares hash values of a pattern and text windows before verifying character matches.
- heuristicAn estimate used to guide choices in a search or optimization problem.
- cost matrixA cost matrix records the cost of each possible worker–task assignment in a row-and-column table.
- bad characterA bad character is a text character that causes a right-to-left pattern comparison to mismatch and determines a pattern shift in Horspool's algorithm.
- height functionA height function assigns labels to network vertices to determine which flow operations are admissible in the push-relabel algorithm.
- right-to-left processingRight-to-left pattern scanning compares a candidate pattern occurrence beginning with its rightmost character and proceeds toward its leftmost character.
- all-pairs shortest pathThe problem of finding the minimum path cost between every pair of vertices in a graph.
- quadratic time complexityA time complexity that grows quadratically with input size, or proportionally to n × m for two input lengths in the stated case.
- rolling hashA rolling hash updates the hash of a sliding window by removing the outgoing value and incorporating the incoming value instead of recomputing the hash from scratch.
- Gale-Shapley algorithmThe Gale-Shapley algorithm, also called deferred acceptance, constructs a stable matching through proposals that can be tentatively accepted and later displaced.
- pheromone depositAn ant colony optimization operation that adds pheromone to traversed edges in proportion to a reward and inversely to tour distance.
- state transition ruleA procedure for choosing among available next states, often by assigning probabilities to alternatives.
- swarm intelligenceSwarm intelligence is collective problem-solving behavior that emerges from interactions among decentralized agents.
- receiverA receiver is a participant on the side that evaluates and tentatively accepts or rejects proposals in a two-sided matching procedure.
- shift valueA shift value is an integer distance specifying how far a search pattern may move after a character mismatch.
- proposerA proposer is a participant role that initiates matching proposals in a deferred-acceptance procedure.
- stabilityA stable matching is an assignment in which no unmatched pair would both prefer each other to their current partners.
- assignment problemThe assignment problem allocates agents to tasks, typically one-to-one, to optimize an objective such as total cost.
- O(n + m)A time bound proportional to the combined lengths n and m of two inputs.
- matchingA matching is an assignment pairing participants from two sets under specified rules.
- informed searchInformed search is a search strategy that uses an estimate of remaining cost to guide which candidate to explore next.
- heuristic desirabilityA measure of a path's desirability in ant colony optimization, calculated here as the inverse of its distance.
- traversalTraversal is the process of visiting the elements of a data structure in sequence to locate or process them.
- distance matrixA distance matrix is a square matrix whose entries represent distances between pairs of vertices or locations.
- column reductionColumn reduction subtracts a column’s minimum value from every entry in that column.
- row reductionRow reduction is the operation of subtracting a row's minimum entry from every entry in that row of a matrix.
- breadth-first searchBreadth-first search is a graph or tree traversal algorithm that explores vertices level by level from a starting vertex.
- independent zeroAn independent zero is a zero matrix entry selected so that no other selected zero lies in the same row or column.
- optimal assignmentAn optimal assignment is a one-to-one assignment whose total cost is minimum among all feasible assignments.
- false positiveA spurious hit is an invalid candidate match caused by different strings producing the same hash value.
- cubic complexityA time complexity that grows proportionally to the cube of the input size.
- adjacency listAn adjacency list is a graph representation that stores each vertex together with a collection of its neighboring vertices.
- graphA graph is a data structure consisting of vertices and edges that represent entities and relationships.
- adjacency matrixAn adjacency matrix is a two-dimensional array whose entries indicate whether pairs of graph vertices are connected.
- costA cost is a quantity representing the expense or disadvantage associated with a preference or match.
- proper prefixA proper prefix is a sequence at the beginning of a string that is strictly shorter than the entire string.
- uncovered numberAn uncovered number is a matrix entry not crossed by any of the lines covering the current zero entries.
- tradeoffA trade-off is a situation in which improving one property of a solution requires accepting a reduction in another property.
- string matchString matching is the computational task of locating exact or approximate occurrences of one character sequence within another.
- binary treeA binary tree is a tree in which each parent node has at most two child nodes.
- depth-first searchDepth-first search traverses a tree or graph by exploring a path as deeply as possible before backtracking to another branch.
- treeA tree is a hierarchical data structure in which every node descends from a single root and edges flow downward without loops.
- positive feedbackA reinforcing process in which an outcome strengthens the conditions that produce more of that outcome.
- patternA pattern is a character sequence whose occurrence is sought within a text during string matching.
- excluded set XThe excluded set X contains vertices already processed in a Bron-Kerbosch search branch, preventing duplicate clique reports.
- complete subgraphA complete subgraph is a subgraph in which every pair of distinct vertices is connected by an edge.
- pivot vertexA pivot vertex is a selected graph vertex used by the pivoting variant of Bron-Kerbosch to restrict which candidate vertices are explored.
- lower boundA lower bound is a limit that a quantity does not asymptotically fall below.
- active nodeAn active vertex is a vertex with positive excess flow that can undergo a push or relabel operation.
- queueA queue is a first-in-first-out data structure that adds elements at one end and removes them at the other.
- stackA stack is a last-in-first-out data structure that adds and removes elements at one end.
- metaheuristicA metaheuristic is a high-level search strategy for finding good solutions to optimization problems, often without guaranteeing a global optimum.
- directed graphA directed graph is a graph whose edges have a specific orientation from a source vertex to a destination vertex.
- undirected graphAn undirected graph is a graph whose edges represent mutual connections without orientation.
- visited setA visited set is a collection of graph vertices already encountered during traversal.
- proposalA proposal is an offer made by a proposer to a potential matching partner during the matching procedure.
- preferenceA preference indicates which potential match a participant favors over another.
- prefix-suffix matchA prefix-suffix match is an equality between a proper prefix and a suffix of a character sequence, represented by their shared length.
- negative-weight edgeA negative edge weight is a numerical edge cost less than zero in a weighted graph.
- flow conservationFlow conservation is the requirement that, at each intermediate vertex, the total incoming flow equals the total outgoing flow.
- full binary treeA full binary tree is a binary tree in which every node has either zero children or exactly two children.
- perfect binary treeA perfect binary tree is a binary tree whose internal nodes have two children and whose leaves all occur at the same depth.
- brute-force searchBrute force is a problem-solving technique that straightforwardly examines possible solutions without applying problem-specific optimization.
- O(nxm)A time bound proportional to the product of text length n and pattern length m.
- preprocessingPreprocessing is preparatory computation performed on input data before the main algorithmic operation begins.
- antA computational agent modeled on an ant that explores routes and leaves virtual pheromone signals in an optimization process.
- greedy best-first searchGreedy best-first search expands the candidate with the most promising heuristic estimate without accounting for the cost already incurred.
- doubly linked listA doubly linked list is a linked list whose nodes contain pointers to both the previous and next nodes.
- arrayAn array is an indexed collection of elements stored in an ordered sequence.
- preference listA preference list records a participant’s possible matches in ranked order.
- cycleA closed path in a graph that returns to its starting vertex.
- source nodeA source node is the vertex from which a graph traversal or route computation begins.
- nodeA node is an element of a linked structure that stores data and one or more links to other nodes.
- pattern shiftA pattern shift is the relocation of a search pattern to a later text position after a comparison result determines that earlier positions can be skipped.
- single-source shortest pathA single-source shortest path algorithm computes shortest-path distances from one starting vertex to other vertices in a graph.
- worst/best-case analysisWorst-case analysis evaluates an algorithm using the maximum resource cost or execution time over inputs of a given size.
- first-in-last-out structureLIFO is an ordering rule in which the most recently added element is the first one removed.
- rightmost occurrenceA rightmost occurrence is the latest-position occurrence of a character within a pattern or sequence.
- rejectionA rejection is a receiver's refusal of a proposal because another available proposal is preferred or the receiver has no capacity to accept it.
- sliding windowThe sliding window technique processes a contiguous portion of a sequence while shifting it incrementally across the sequence.
- logarithmic time complexityLogarithmic time is a complexity class whose execution time grows in proportion to the logarithm of input size.
- linked listA linked list is a sequence of elements connected by links or references to other elements.
- stable matching problemThe stable matching problem asks for a pairing between two groups in which no unmatched pair would both prefer each other to their assigned partners.
- alphabetAn alphabet is a defined set of symbols from which strings are formed.
- scalabilityThe ability of a software system or algorithm to maintain acceptable behavior as workload or resource demands increase.
- item indivisibilityItem indivisibility is the condition that each item must be selected as a whole rather than divided into fractional portions.
- constraintA constraint is a requirement or limitation that restricts which selections or solutions are permitted.
- correctnessThe property of producing results that satisfy the specified requirements for all applicable inputs and conditions.
- knapsack algorithmThe knapsack framework is an optimization approach for selecting indivisible items under a resource capacity while maximizing an associated value.
- leaf nodeA leaf node is a tree node with no children.
- root nodeA root node is the single topmost node of a tree from which every other node descends.
- shortest pathA shortest path is a path between vertices whose total edge weight is minimal among the paths connecting them.
- substringA substring is a contiguous non-empty sequence of characters within a string.
- proper suffixA proper suffix is a sequence at the end of a string that is strictly shorter than the entire string.
- applicant-proposing Gale-Shapley algorithmA Gale-Shapley algorithm variant in which applicants are the proposing side of the matching process.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
