Glossary

101 terms from Algorithms Beyond the Basics in C++, in plain words, each with the chapter that teaches it.

Search the glossary

#

0/1 knapsack: A problem where each item (like one of Jo's roast batches) is taken whole or not at all, and you want the most total value that fits within a limit such as 60 minutes of roaster time. It is solved with a 2D table where each cell chooses between skipping and taking a batch.

A

adjacency list: A way to store a graph as a map from each place to a vector of its neighbors. In a weighted graph, each neighbor entry also carries the edge's weight, such as a road's driving minutes.
auto [a, b] (structured binding): C++ syntax that unpacks a pair, tuple or struct into separate named variables in one line, such as `auto [value, chosen] = knapsack(...)`.

B

Backtracking: Building an answer one choice at a time by choosing, exploring the rest by recursion, then undoing the choice so the next one starts clean. It lists every subset or ordering, such as Alex's café routes.
base case: The simplest case of a recursive function, where it stops calling itself and returns an answer directly, such as when every item has been decided in `subsets`.
Bellman-Ford: A shortest-path algorithm that still works when some edges have negative weights, where Dijkstra's algorithm fails. It is slower than Dijkstra's algorithm, so it is used only when negative weights are possible.
BFS (breadth-first search): A graph search that explores outward from a start, finding the route with the fewest roads. It is not enough when roads have different driving times, because the fewest roads is not always the fastest route.
Big-O: A way to describe how an algorithm's running time or memory grows as the input size n grows, such as O(n) or O(n²). It ignores constant factors and focuses on the growth trend.
binary: Writing whole numbers with only 0s and 1s, where each digit (a bit) is worth 1, 2, 4, 8 and so on from the right, so `1101` means 13. In C++ a `0b` prefix writes a number in binary in code, so `0b1101` is 13.
bit operators: Operators that work on each bit column separately: `&` (and), `|` (or), `^` (xor), `~` (not), and `<<`/`>>` which shift bits left or right, doubling or halving the number.
bitmask: A number whose individual bits stand for on/off options, like grind, gift wrap and express on an order; each single option is a flag. You set flags with `|`, test with `&` and clear with `& ~`.
Bottom-up: Dynamic programming that fills a table starting from the smallest case, so each bigger answer just reads earlier ones. It uses no recursion, so the call stack can't overflow.
brute force: A solution that tries every possibility. It is slow but easy to get right, so it gives answers to check a faster version against.

C

call stack: The memory where each active function call is kept while it runs. Very deep or endless recursion fills it up and crashes the program, which bottom-up DP avoids.
catch block: C++ code that handles an exception thrown inside a `try` block, such as the `runtime_error` Kahn's algorithm throws on a cycle. `what()` returns the error message.
choice tree: All the choices a backtracking search can make, drawn level by level, like yes/no for each add-on. Each path to the end is one answer.
compressed trie: A trie that saves memory by storing runs of single-child letters, such as "oliday blend", in one node.
connected component: A group of items all joined to each other, directly or through others, such as cafés pooled into one delivery.
const reference (const T&): A way to pass a value to a function without copying it. A plain `&` lets the function change the caller's variable, while `const` forbids changes.
constexpr: A keyword marking a value as a fixed constant known when the program is compiled, used for flag values like `GRIND = 1`.
contains: A C++20 member function asking whether a map or set has a given key.
CSV (comma-separated values): A plain text file format with one record per line and fields separated by commas, like `roads.csv` and `batches.csv`.
Cycle: A path in a directed graph that leads back to where it started, such as 'bag before roast' and 'roast before bag'. Tasks on a cycle can never be ordered.

D

DAG (directed acyclic graph): A directed graph with no cycles, like Jo's morning tasks. A topological order exists only for a DAG.
dependency: When task B can't start until task A is done, B has a dependency on A, such as roasting waiting for green beans to arrive.
DFS (depth-first search): A graph search that follows one path as deep as it can before backing up. Backtracking walks its choice tree this way.
Dijkstra's algorithm: An algorithm that finds the fastest route from a start to every other place by always handling the closest unhandled place next, using a min-heap. It requires weights of zero or more.
directed edge: An arrow from one vertex to another, used to show an 'A before B' rule between tasks. A graph made of such arrows is a directed graph.
Dynamic programming: Solving a problem by building on answers to smaller, overlapping subproblems. It applies when the same smaller question repeats and the big answer is built from smaller ones.

E

edge case: An input at the limits, such as an empty list, one item, all items equal, duplicates or a missing target. Testing these catches bugs examples miss.
edit distance: The smallest number of single-letter changes (insertions, deletions or replacements) that turn one word into another. It is a classic 2D dynamic programming problem.

F

factorial (n!): n × (n − 1) × ... × 1, the number of ways to order n items. It grows much faster than 2ⁿ, so listing all orders only suits about 10 items.
Fenwick tree: A data structure that supports fast range totals even while the values change. It answers sum queries and applies updates in O(log n) time.
fixed-width integer: A C++ integer type with a set number of bits (usually 32 for `int`); `unsigned` has no negative values and behaves predictably for bit work, and `long long` holds about 9.2 × 10¹⁸.
Floyd-Warshall: An algorithm that finds the shortest path between every pair of places in a weighted graph. It runs in O(V³) time for V places.

G

g++ -O2: Compiler flags: `-std=c++20` selects the language version, `-Wall -Wextra` turn on warnings, and `-O2` optimizes the code; compiled this way, C++ does roughly 10⁸ simple steps a second.
Greedy algorithm: An approach that takes the best-looking choice at each step and never undoes it. It is fast but only correct when something like a swap argument shows the choice is safe; it fails for $10, $25 and $30 gift cards.

H

hash (std::hash): The function that lets a key be stored in an `unordered_map`. Numbers and strings have one, but pairs and vectors don't, so those keys need `std::map`.

I

In-degree: The number of arrows pointing into a vertex, meaning how many tasks it waits for. A task with in-degree 0 can start now.
INF: A big constant such as `1'000'000'000` meaning 'not possible yet' or 'no route found yet'. It loses every smaller-is-better comparison, and adding 1 to it does not overflow. The `'` in the number is a digit separator that only makes it easier to read.
Interval: A stretch of time with a start and an end, stored as a `std::pair<int, int>` in minutes since midnight. Two intervals overlap when each starts before the other ends.
Interval scheduling: Choosing the most non-overlapping bookings, like for Kettle & Crane's cupping room, by sorting by end time and taking each one that fits.

K

Kahn's algorithm: A topological sort that repeatedly takes a task with in-degree 0, adds it to the order, and lowers the in-degree of the tasks after it. If the order comes out short, there is a cycle.
KMP (string matching): The Knuth-Morris-Pratt algorithm for finding a short pattern inside a longer text quickly. It runs in O(n + m) time by reusing what it already matched instead of starting over after a mismatch.
Kruskal's algorithm: A greedy way to build a minimum spanning tree: go through roads shortest first and keep each road that joins two places not yet connected, using union-find to check.

L

lambda: A small unnamed function written inline, such as the one that tells `std::sort` to order bookings by end time.
longest common subsequence: A classic dynamic programming problem: find the longest sequence of items that appears in the same order, though not necessarily side by side, in two inputs.

M

Memoization: Saving each answer the first time you work it out, so a repeated call is just a lookup. It cut `ways(30)` from 2.7 million calls to 59.
merging intervals: Joining overlapping or touching time periods, like Alex's delivery windows, by sorting by start and stretching the last period's end.
min-heap: A structure where the smallest item comes out first. In C++ it is a `std::priority_queue` with `std::greater<>`, used for Dijkstra's algorithm, counting rooms and the roast scheduler.
minimum spanning tree: The set of roads that joins every place with the smallest total weight and no loops. Alex needs one to know which roads to plow.

N

negative weight: An edge that lowers the total, like a rebate on a delivery fee. It breaks Dijkstra's algorithm.
nullptr: The null pointer, meaning 'points to nothing'. `find_node` returns it when a text isn't in the trie.

O

Optimal substructure: A feature where the best answer to the big problem is built from best answers to smaller ones, like `ways(n)` from `ways(n - 1)` and `ways(n - 2)`.
overflow: When a number gets too big for its type, such as a `long long` past about 9.2 × 10¹⁸. For signed integers this is undefined behavior with no warning.
Overlapping subproblems: The same smaller question asked many times, like `ways(28)` being needed by both `ways(29)` and `ways(30)`.

P

Path compression: A union-find trick where `find` points every item it passed straight at the root, so the next walk takes one step.
Permutation: One order of all the items, such as one order in which Alex visits three cafés. n items have n! permutations.
popcount: A C++20 function from `<bit>` that counts the 1 bits in an unsigned number, telling how many options an order has.
power of two: A number such as 1, 2, 4, 8 with exactly one 1 bit. `(n & (n - 1)) == 0` is true for these when n is above 0.
prefix: The start of a word, such as 'ho' for 'house blend'. A trie is also called a prefix tree.
Prim's algorithm: A way to build a minimum spanning tree by starting from one place and repeatedly adding the cheapest edge that reaches a new place, using a heap to find that edge. It produces the same total weight as Kruskal's algorithm.
Pruning: Cutting off a branch of the search as soon as it can't lead to an answer, such as stopping when a gift box total passes $45.

R

Relaxing an edge: Updating a place's best known time when going through another place gives a faster route.
Root (union-find): The member that stands for a whole group; it is its own parent. Two items are in the same group when following parents reaches the same root.
runtime_error: A standard C++ exception type thrown for problems found while a program is running, such as a cycle in a set of task rules or a missing file. A `catch` block can receive it and read its message with `what()`; more specific types such as `domain_error` let code tell one kind of problem from another.

S

segmentation fault: A crash caused by invalid memory access; here it usually comes from endless or very deep recursion overflowing the call stack, or reading a null pointer.
Shortest path: The route with the smallest total weight, such as the fewest minutes, which can differ from the route with the fewest roads.
Sliding window: A run of neighboring items that moves along a list, updating its total in O(1) per step by adding the item coming in and dropping the one going out.
Slow and fast pointers: Two indexes moving the same way over a vector: `fast` reads every item and `slow` marks the end of the tidy part, as when removing duplicate order IDs in place.
stale entry: An old heap item in Dijkstra's algorithm whose minutes are larger than the place's current best, so it is skipped with `continue`.
static local variable: A variable declared inside a function with `static`; it is created on the first call and keeps its value between calls. It is handy for hiding a memo map inside a function so callers never see it.
std::accumulate: A function from `<numeric>` that adds up a range of values, used here for the first window's total.
std::bitset: A standard-library type holding a fixed number of bits that prints all of them with leading zeros, such as `bitset<8>(13)` printing `00001101`.
std::format: The C++20 way to build text with aligned columns, using codes like `{:<6}` and `{:02d}`; it needs g++ 13 or newer.
std::map: The ordered, tree-based map that keeps keys sorted and only needs `<` to compare them. It works with pairs and vectors as keys, which `unordered_map` can't take.
std::optional: A type that holds either a value or nothing; `std::nullopt` means 'no value'. `pair_for_card` uses it to say 'no pair found'.
std::pair: A type holding two values, accessed as `.first` and `.second`. Pairs compare by first, then second, so they sort and work in heaps.
std::queue: A first-in, first-out container: items leave from the front in the order they arrived. Kahn's algorithm uses one for tasks that are ready, and `pop()` returns nothing, so read `front()` first.
std::set: An ordered collection of unique items that keeps them sorted and supports fast lookup with `contains`. It can hold things like the closed street corners in a grid.
std::sort: The standard function that sorts a range, optionally with a comparator lambda; it costs O(n log n).
std::stringstream: Tools for reading text: `ifstream` reads a file, `stringstream` treats a string as a stream, and `getline` with a `','` separator cuts a CSV line into pieces.
std::tuple: Like a pair but with any number of fields. Kruskal's code stores each road as `tuple<int, string, string>`, which sorts field by field.
std::unique_ptr: A smart pointer that owns what it points to and deletes it automatically. Each trie node owns its children this way, so there are no leaks and no `delete`.
std::unordered_map: A hash-based map (or set) with fast lookups and no fixed key order. Keys need a hash and an equality test.
STL (Standard Template Library): The part of the C++ standard library with containers and algorithms, such as `std::unique` for removing duplicates.
struct: A class whose members are public by default, used to group related values such as a `Batch` with its name, minutes and value.
subarray: A run of neighboring items in a list, which is a clue pointing to a sliding window.
subset: Any selection of items from none to all of them. n items give 2ⁿ subsets, such as the 8 combinations of three add-ons.
swap argument: A way to show a greedy choice is safe: swap the first choice of any best answer for the greedy one and show the result is no worse.

T

top-down: Dynamic programming that starts with the big question and recurses down, saving answers as it goes; memoization is this style.
Topological order: An order of tasks in which every task comes after everything it depends on. There can be more than one valid order.
Trie: A tree of letters where words with the same start share a path and a flag marks where a word ends. It powers autocomplete for the shop's search box.
Two pointers: A pattern with two indexes moving through one list, either from both ends of a sorted list or in the same direction.
type alias (using): A `using` line that gives a long type a short name, such as `using Choices = std::vector<std::string>;`.

U

undefined behavior: What happens when C++ code does something the language doesn't define, such as reading past a vector's end or overflowing a signed integer. The result can be garbage or a crash, with no warning.
union by size: A union-find trick that hangs the smaller group under the bigger group's root so paths grow slowly.
Union-find: Also called disjoint set union: a structure that keeps items in groups and answers 'same group?' almost instantly, with `find` to get a group's root and `union` to join two groups. Sam uses it to track pooled café orders.

V

vector of vectors: A table made of one vector per row, such as `best[i][t]` in the knapsack. Each row must be its own separate vector.

W

Weighted graph: A graph whose edges carry numbers, such as the driving minutes on Alex's roads.

X

XOR: A bit operation giving 1 where two bits differ. Since `x ^ x` is 0, XORing a list cancels pairs, leaving the one unpaired order ID.