Glossary

97 terms from Algorithms Beyond the Basics in Rust, in plain words, each with the chapter that teaches it.

Search the glossary

#

0/1 knapsack: A problem where each item is taken whole or not at all, and you want the most value that fits within a limit. Jo picks roast batches worth the most dollars that fit in her remaining roaster minutes.

A

A* (A-star): A shortest-path algorithm that speeds up the search for a single goal by using an estimate of the distance still left to travel. It is a guided variant of Dijkstra's algorithm.
Adjacency list: A way to store a graph as a map from each place to its neighbors. In a weighted graph, each neighbor is stored together with its edge weight, such as driving minutes.
Autocomplete: Suggesting every stored word that starts with what the customer has typed so far, such as products after typing "ho" in the Kettle & Crane search box.

B

Backtracking: A way to build every possible answer one choice at a time: make a choice, explore the rest, then undo the choice. It suits small inputs like the add-ons for an order.
Base case: The situation in 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. It is slower than Dijkstra's algorithm.
BFS (breadth-first search): A graph search that spreads out from the start one road at a time, so it finds the route with the fewest roads. It ignores driving minutes, which is why Dijkstra's algorithm is needed.
Big-O: A way to describe how the running time or memory of an algorithm grows as the input grows, such as O(n) or O(n log n). It ignores constant factors and focuses on the growth rate.
Binary / bit: Binary writes numbers using only 0s and 1s, and each digit is a bit. From the right the bits are worth 1, 2, 4, 8 and so on, so `1101` is 13.
BinaryHeap: Rust's heap type, which always hands back its largest item first. Wrapping entries in `Reverse` turns it into a min-heap that returns the smallest.
Bit methods (count_ones, from_str_radix): `n.count_ones()` counts the 1 bits in a number, such as how many options an order has switched on. `from_str_radix("1101", 2)` reads text written in a given base and returns a `Result` because the text might not be valid.
Bit operators: Operators that work on each column of bits: `&` (and), `|` (or), `^` (XOR), `!` (not), and `<<` / `>>` that shift bits left or right. A shift left doubles a number and a shift right halves it.
Bitmask / flag: A bitmask is one number whose bits stand for on/off options, and each option is a flag. An order's grind, gift wrap and express choices can all live in one `u32`.
Bottom-up (tabulation): Dynamic programming that fills a table from the smallest case upward, with no recursion. Each bigger answer just reads earlier ones, so the stack cannot overflow.
Brute force: A solution that tries every possibility. It is slow but easy to get right, so you write it first and use it to check the faster version.

C

came_from (route rebuilding): A map that records, for each place, the place you came from when you found its fastest time. Following it back from the goal to the start (then reversing) rebuilds the route.
Choice tree: A picture of all the choices a backtracking search can make, level by level. Each path to the end is one answer.
Closure: A small unnamed function written inline, like `|b| b.2` in `sort_by_key`, which here picks out a booking's end time.
Compressed trie: A trie that saves memory by storing a run of single-child letters, such as "oliday blend", in one node.
Connected component: A group of items that are all joined to each other, directly or through others. Each union-find group is one, like a pool of cafés sharing a delivery.
Copy (of a vector): `chosen.clone()` makes a new vector with the same items, so later undo steps in backtracking cannot change a saved answer.
CSV (comma-separated values): A plain text file where each line is a record and the fields are separated by commas, like `Roastery,Burnside,6`. Programs can read it line by line and split each line at the commas.
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 put in order.

D

DAG (directed acyclic graph): A graph whose edges have a direction and which has no cycles. Only a DAG of tasks can have a valid topological order.
Debug build: A build made without `-O`. It runs 10 to 50 times slower than an optimized build and also panics on integer overflow, so time the optimized build.
Dependency: A task that must be done before another can start. Roasting depends on the green beans arriving.
Derive: An attribute like `#[derive(Clone)]` placed above a struct that makes Rust write standard methods for it, such as `clone`, `==` or `default`.
DFS (depth-first search): A graph search that follows one path as deep as it can before backing up to try another. Backtracking walks its choice tree this way, and it can also be used to put tasks in topological order.
Dijkstra's algorithm: An algorithm that finds the fastest route from one place to all others by always handling the closest unhandled place next, using a min-heap. It needs weights of zero or more.
Directed graph: A graph whose edges point one way, from A to B only, such as "A must happen before B". An undirected connection, like a two-way road, can be stored as two directed edges, one in each direction.
Dynamic programming: Solving a problem by building on answers to smaller overlapping problems. It works when the problem has overlapping subproblems and optimal substructure, and can be done top-down or bottom-up.

E

Edge case: An input at the limits, such as an empty list, one item, duplicates or a missing target. You test these against the brute force.
Edit distance: The smallest number of single-letter changes (insertions, deletions or substitutions) needed to turn one word into another. It is a classic 2D dynamic programming problem.
entry / or_default: A `HashMap` pattern that finds a key's value or creates an empty one if the key is missing, such as the first road seen for a place. It is also how a trie adds a node for a new letter.
Exponential time: Work that doubles (or more) with every extra item, like listing all subsets (2ⁿ) or the plain shelf recursion (about 1.6ⁿ). It is only affordable for small inputs, roughly n up to 25.

F

Factorial (n!): n × (n − 1) × ... × 1, the number of orders of n items. It grows even faster than 2ⁿ: 10 items have 3,628,800 orders.
Fenwick tree: A data structure that gives fast range totals over a sequence of values while still allowing the values to be updated. It is related to segment trees, which serve the same purpose.
Floyd-Warshall: A shortest-path algorithm that finds the best route between every pair of places at once.

G

Greedy algorithm: An algorithm that takes the best-looking choice at each step and never goes back. It is fast, but only correct when something like a swap argument shows the choice is safe.
Greedy choice: The option that looks best right now, taken at each step of a greedy algorithm, such as the biggest coin or the booking that ends first.

H

Hash and Eq: The two traits a type needs to be a `HashMap` key or `HashSet` item. Integers, strings, chars and tuples of them qualify, but `f64` does not because NaN is not equal to itself.
HashSet: A collection of unique values with fast O(1) membership checks. It tracks which cafés are already in a route, or which corners are closed.

I

In-degree: The number of edges pointing into a vertex, meaning how many tasks it waits for. Tasks with an in-degree of 0 can start now.
Interval: A stretch of time with a start and an end, stored as a `(start, end)` tuple of minutes since midnight.
Interval scheduling: Choosing the most non-overlapping bookings for one room. The greedy rule is to sort by end time and take each booking that starts at or after the last one chosen ends.

K

Kahn's algorithm: A way to produce a topological order: put tasks with in-degree 0 in a queue, take them one by one, and lower the in-degree of what follows. If the order comes out short, there is a cycle.
KMP (Knuth-Morris-Pratt): A fast string-matching algorithm that finds a pattern inside a longer text in linear time. It avoids rechecking letters by using what it has already matched.
Kruskal's algorithm: A way to build a minimum spanning tree by going through roads from shortest to longest and keeping each one that joins two places not yet connected. It uses union-find to check this.

L

Lifetime ('a, 'static): Rust labels that say how long borrowed data lives. `'static` string literals live for the whole program, and `'a` says returned names are the same borrowed names that came in.
Longest common subsequence: A classic 2D dynamic programming problem: find the longest sequence of letters that appears in the same order, though not necessarily side by side, in two strings.

M

Memoization: Saving each answer the first time you compute it, in a `HashMap` or `Vec`, so a repeated call is just a lookup. It turns the shelf-count recursion from 2.7 million calls into 59.
Merging intervals: Joining overlapping or touching intervals into busy periods: sort by start, then stretch the last period's end when the next interval starts before (or at) it. It costs O(n log n).
Min-heap: A heap that hands back its smallest item first. Rust's `BinaryHeap` is a max-heap, so wrapping entries in `Reverse` gives min-heap behavior, as used for interval end times and Dijkstra's distances.
Minimum spanning tree: The cheapest set of edges that links every vertex with no loops, such as the fewest plowed minutes that keep every place reachable.

N

Negative weight: An edge that lowers the total, like a rebate on a delivery fee. It breaks Dijkstra's algorithm, so Bellman-Ford is used instead.

O

Optimal substructure: A problem has this when the best answer to the big question is built from best answers to smaller ones, like `ways(n)` from `ways(n - 1)` and `ways(n - 2)`.
Overlap: Two intervals overlap when each starts before the other ends. Back-to-back bookings, where one ends exactly when the next starts, do not overlap.
Overlapping subproblems: When the same smaller question is asked again and again, as `ways(28)` is inside both `ways(30)` and `ways(29)`. It is the main sign that DP will help.

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. Alex's three cafés can be visited in 6 orders, and n items have n! (n factorial) orders.
petgraph: A Rust crate (outside the standard library) that provides graph data structures and graph algorithms, including topological sort.
Power of two: A number such as 1, 2, 4, 8 that has exactly one 1 bit. `n & (n - 1) == 0` is true for positive powers of two, and each flag in a bitmask uses one.
Prefix: The start of a word, such as "ho" in "house". A trie stores words so that words sharing a prefix share a path.
Prim's algorithm: Another way to build a minimum spanning tree, by growing one tree outward from a starting place using a heap.
Pruning: Cutting off a branch of the search as soon as it can't lead to an answer, like stopping once a gift box already costs more than $45.

R

Rebuilding the choice: After filling a DP table, walking back from the last cell and comparing each cell with the one above to learn which items were taken, not just the best value.
Relaxing an edge: Lowering a place's best known time because a road through the current place gives a faster route. Dijkstra's algorithm does this for each road out of the place it pops.
Reverse: A wrapper that flips the order of a value so Rust's max-heap `BinaryHeap` acts as a min-heap and pops the smallest item first.
Rooms needed: The most bookings that overlap at once. Sort by start time and keep a min-heap of end times: reuse the room that frees first if it is free, and the largest heap size is the answer.
Root (union-find): The one member that stands for a whole group. Two items are in the same group when following parents up from each reaches the same root.
rustc -O: The command that compiles a single Rust file, with `-O` turning on optimizations so timings are realistic.

S

Sentinel value (u32::MAX, saturating_add): `u32::MAX`, the largest `u32` (4,294,967,295), stands in for "not possible yet" or "no route found yet" because it loses every `<` comparison. Adding 1 to it would overflow, so `saturating_add(1)` stops at the maximum instead.
Shortest path: The route with the smallest total weight, such as the fewest driving minutes, which is not always the route with the fewest roads.
Slice: A borrowed view of part or all of a vector or array, such as `&[i32]`, so one function accepts both. `&mut [i32]` is a slice the function may change.
Sliding window: A run of neighboring items that moves along a slice, updating the running total by adding the new item and dropping the old one. It can be fixed in size, or grow and shrink.
Slow and fast pointers: Two indexes that move the same way: the fast one reads every item and the slow one marks the end of the tidy part, as when removing duplicate order IDs in place.
Stable sort: A sort that keeps items with equal keys in their original relative order. `sort_by_key` in Rust is stable.
Stack overflow: A crash when recursion goes too deep for the program's call stack. Bottom-up tables avoid it because they use loops.
Stale entry: An old entry in Dijkstra's heap holding a slower time for a place that has since been reached faster. When popped it is skipped with `continue`.
Subset: Any selection of the items, from none to all. n items have 2ⁿ subsets, which backtracking or a bitmask can list.
Swap argument: A way to show a greedy choice is safe: take any best answer, swap its first choice for the greedy one, and show it gets no worse.

T

Timing code (Instant, black_box): `Instant::now()` takes a start time and `.elapsed()` tells how long has passed. `black_box` stops the compiler from noticing a result is known and skipping the work, so the timing measures the real cost.
Top-down: Dynamic programming that starts from the big question and recurses down to smaller ones, saving answers with memoization.
Topological order: A list of tasks where each 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 the same path, and an `is_word` flag marks where a word ends. Lookups cost one step per letter, however many words are stored.
Two pointers: Keeping two indexes into the same slice, either moving inward from both ends of a sorted slice or moving the same way, to solve problems in one pass.
Type alias: A short name for a long type, such as `type Graph = HashMap<String, Vec<(String, u32)>>`.

U

Union by size: A union-find trick that hangs the smaller group's root under the bigger one's, so paths stay short.
Union-find: A structure that keeps items in groups, with `find` to get a group's root and `union` to join two groups, both nearly O(1). Sam uses it to see which cafés share a pool.
unwrap / expect: Rust methods that take the value out of an `Option` or `Result` and stop the program if it is `None` or `Err`. `expect` adds a message of your own.
usize: Rust's unsigned number type for indexes and lengths. It can't go below 0, so `len() - 1` on an empty slice or `t - minutes` can panic.

V

VecDeque (queue): A queue where items enter at the back and leave from the front. Kahn's algorithm uses one to hold ready tasks in the order they became ready.
Vector of vectors: A 2D table made of one `Vec` per row, built with `vec![vec![0; w]; h]`. The knapsack's `best[i][t]` table is one.
Vertex and edge: The points and the links of a graph. A vertex is a task or place, and an edge is a rule or road between two.

W

Weighted graph: A graph whose edges carry numbers, such as the driving minutes on each road of Alex's delivery map.

X

XOR (exclusive or): A bit operation that gives 1 where two bits differ. Because `x ^ x` is 0, XORing a list cancels pairs and leaves the one unpaired value.