Glossary

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

Search the glossary

#

0/1 knapsack: The problem of choosing items, each taken whole or not at all, to get the most value within a limit. Jo uses it to pick roast batches that fit her minutes on the roaster.
@cache: A decorator from Python's `functools` module that gives a function its own memo dict. Calls with the same arguments, such as `ways_fast(100)`, are then answered by lookup instead of being recomputed.

A

A* (A-star): A shortest-path algorithm that speeds up the search for one goal by using a guess of the distance still left. It is mentioned as something to look up later.
Adjacency list: A way to store a graph as a dict from each place to the list of its neighbors. In a weighted graph each neighbor is stored as a `(neighbor, minutes)` tuple.
Autocomplete: Suggesting every stored word that starts with what the user has typed so far. The Kettle & Crane search box does this with a trie.

B

Backtracking: A way to list every possible answer by building it one choice at a time: choose, explore, undo. It suits small inputs, such as every set of add-ons a customer could pick.
Base case: The simplest situation in a recursive function, where it returns an answer directly without calling itself again. In `subsets` it is reached when every item has been decided.
Bellman-Ford: A shortest-path algorithm that still works when some edges have negative weights, though it is slower than Dijkstra's algorithm.
BFS (breadth-first search): A graph search that finds the route with the fewest roads. It is not enough when roads have different driving times, because the route with fewest roads can take longer, so a weighted method such as Dijkstra's algorithm is needed.
Big-O: A rough way to describe how a program's running time or memory grows with the input size n, such as O(n) or O(n²). It is used to compare how well different solutions scale.
Binary: Writing 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 is 8 + 4 + 0 + 1 = 13. In Python, `0b1101` writes 13 in binary, `bin()` shows a number's bits and `int(text, 2)` reads binary text.
Bit operators: Python operators that work on the bits of whole numbers one column at a time: `&` (and), `|` (or), `^` (XOR), `~` (not), and the shifts `<<` and `>>`. Each left shift doubles a number (`5 << 3` is 40, and `1 << n` is 2ⁿ) and each right shift halves it.
bit_count(): An integer method (Python 3.10+) that counts the 1 bits in a number, such as how many options an order has switched on.
Bitmask: A single number whose bits each stand for an on/off option; one such option is a flag. For example, grind, gift wrap and express shipping can be stored as bits 1, 2 and 4 of one number.
Bottom-up (tabulation): Dynamic programming that fills a table from the smallest case upward, so each answer reads earlier ones. It uses no recursion and so avoids `RecursionError`.
Brute force: A solution that tries every possibility. It is slow but easy to get right, so it serves as a check on a faster version.

C

Choice tree: A drawing of all the choices a backtracking search can make, one level per decision. Each path from the top to the end is one answer.
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. Union-find tracks these groups, such as the cafés pooling orders.
Copy (of a list): A new list with the same items, made with `chosen[:]`. Saving a copy at the base case keeps later undo steps from changing the saved answer.
CSV (comma-separated values): A plain text file with one record per line and values separated by commas, such as `Roastery,Burnside,6`. In Python it can be read line by line with `open`, then `strip()` and `split(",")` to get the values.
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 directed graph with arrows and no cycles, so a valid order of its vertices exists. Jo's morning tasks form a DAG.
Decorator: A function that takes your function and hands back a changed version of it. You apply it by writing `@name` on the line above `def`.
Dependency: A task that must be finished before another can start. For example, roasting depends on receiving the beans.
deque: A queue from Python's `collections` module where items are added at one end and leave from the front with `popleft()`. Kahn's algorithm uses one for the ready tasks.
DFS (depth-first search): A graph search that follows one path as far as it can before backing up. A backtracking search 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 needs edge weights of zero or more.
Dynamic programming: Solving a problem by building on answers to smaller problems that repeat, saving each so it is worked out only once. It applies when there are overlapping subproblems and optimal substructure.

E

Edge (graph): In a graph, a vertex is a point such as a place or task, and an edge is a link between two of them, such as a road or an "A before B" rule.
Edge case: An input at the limits, such as an empty list, one item, duplicates or a missing target. Testing these catches mistakes that normal examples miss.
Edit distance and longest common subsequence: Two classic problems solved with a 2D dynamic programming table: edit distance counts the letter changes that turn one word into another, and the longest common subsequence finds the longest run of letters that appear in both words in the same order.
enumerate: A Python built-in that gives each item of a loop together with its position. The CSV loaders use it to skip line 0, the header row.

F

float("inf"): A float that is larger than every number, used to mean "not possible yet" or "no route found yet". Because any real value compares smaller, it loses every comparison when looking for the smallest value.
Floyd-Warshall: A shortest-path algorithm that finds the best route between every pair of places at once. It is mentioned as something to look up later.
Format codes: Short codes inside an f-string's braces that control how a value prints, such as `:02d` (zero-padded), `:<6` (left-aligned), `:,` (thousands commas) and `:03b` (binary).

G

graphlib: A Python standard-library module with a `TopologicalSorter` class. It takes a dict from each task to the tasks it depends on, and `static_order()` returns a valid order or raises `CycleError`.
Greedy algorithm: An algorithm that takes the best-looking choice at each step and never undoes it. It is fast but is correct only when a reason, such as 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. For interval scheduling it is the booking that ends first.

H

Hashable: Able to be used as a dict key, as numbers, strings and tuples can. Lists are unhashable, so `@cache` raises `TypeError` if you pass one.
heapq: Python's standard-library module for heaps. `heappush` adds an item and `heappop` removes the smallest in O(log n).

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.
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 bookings that don't overlap by sorting by end time and taking each booking that starts at or after the last chosen one ends. Priya uses it for the cupping room.

K

Kahn's algorithm: A way to produce a topological order by repeatedly taking a task with in-degree 0 and lowering the in-degrees of the tasks after it. If the order comes out short, there is a cycle.
Kruskal's algorithm: A greedy way to build a minimum spanning tree: go through the roads from shortest to longest and keep each one that joins two places not yet connected. Union-find does the checking.

L

lambda: A short anonymous function written inline. `key=lambda b: b[2]` tells `sorted` to sort bookings by their end time.
List of lists: A two-dimensional table made of one list per row, built with a loop so every row is its own list. The knapsack's `best[i][t]` is one.

M

Memoization: Saving each answer the first time you work it out, then looking it up when the same question comes again. It cut `ways(30)` from 2.7 million calls to 59.
Merging intervals: Joining overlapping or touching intervals into busy periods by sorting by start time and stretching the last period's end. Alex uses it for the van's delivery windows.
Min-heap: A structure that always gives you its smallest item quickly. Dijkstra's algorithm uses one to get the nearest place, and the room counter uses one for the earliest end time.
Minimum spanning tree: The cheapest set of edges that links every vertex, with no loops. Alex uses one to find which roads to plow.

N

Negative weight: An edge that lowers the total, such as a rebate on a delivery fee. It breaks Dijkstra's algorithm, which assumes roads only add time.

O

Optimal substructure: A property where 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. A booking that starts exactly when another ends does not overlap it.
Overlapping subproblems: The same smaller question asked many times inside a recursion. For example, `ways(29)` and `ways(30)` both need `ways(28)`.

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; n items have n! (n factorial) orders. For example, Alex's three cafés can be visited in 6 orders.
Power of two: A number such as 1, 2, 4, 8... that has exactly one 1 bit. For positive n, `n & (n - 1) == 0` is true only for powers of two.
Prefix: The start of a word, such as "ho" in "house". A customer's typed text is a prefix that the search box completes.
Prim's algorithm: Another way to build a minimum spanning tree: grow 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. In the $45 gift box, once the total passes $45, the loop `break`s.

R

RecursionError: The error Python raises when recursion goes too deep, such as `ways_fast(5000)`. Bottom-up tables avoid it because they don't recurse.
Relaxing an edge: Updating a place's best known time because a road gives a faster way there. Dijkstra's algorithm relaxes a road when `new < dist[neighbor]`.
Rooms needed: Finding the most bookings that overlap at once by going through them in start order with a min-heap of end times. A room is reused when the earliest end is at or before the next start.
Root (union-find): The member that stands for a whole group in union-find; it is its own parent. Two items are in the same group when following parents leads to the same root.

S

Shortest path: The route with the smallest total weight, such as the fewest driving minutes. It is not always the route with the fewest roads.
Slice: A way to take part of a list with `list[start:stop:step]`. `[:]` copies a whole list and `[::5]` takes every fifth item.
Sliding window: A run of neighboring items that moves along a list one step at a time, updating its total by adding the item coming in and subtracting the one leaving, so each step is O(1). A fixed-size window always covers k items; a variable window grows on the right and shrinks on the left.
Slow and fast pointers: Two indexes moving the same way, where `fast` reads every item and `slow` marks the end of the tidy part. Sam's order IDs are de-duplicated this way.
Stale entry: An old heap entry with a slower time for a place that has since been reached faster. Dijkstra's algorithm skips it when popped.
Subset: Any selection of the items, from none to all; n items have 2ⁿ subsets. Backtracking or a bitmask can list them.
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

Top-down: Dynamic programming that starts from the big question and recurses to smaller ones, saving answers with memoization.
Topological order: An ordering of tasks in which each one comes after everything it depends on. There can be several valid orders.
Trie: A tree of letters where words with the same start share the same path. Each node has a `children` dict and an `is_word` flag, so lookups cost one step per letter.
try / except: Python's way to catch an error so the program can print a clear message instead of crashing. The roast-schedule main block catches the `ValueError` raised for a cycle.
Two pointers: A pattern that keeps two indexes into one list, either moving in from both ends of a sorted list to find a pair or moving the same way. It gives O(n) time with O(1) extra memory.

U

Union by size: A union-find trick of hanging the smaller group's root under the bigger group's root, so the paths stay short.
Union-find: A structure, also called disjoint set union, that tracks which items are in the same group as links arrive, using `find` and `union`. Each call is nearly O(1) with path compression and union by size.

W

Weighted graph: A graph whose edges carry numbers, such as the driving minutes on each of Alex's roads. It is stored as `(neighbor, minutes)` tuples.
with open: Python's way to read a file, where the file closes itself when the block ends. If the file is missing, `open` raises `FileNotFoundError`.

X

XOR: A bit operator that gives 1 where two bits differ. Since `x ^ x` is 0, XOR-ing a list cancels pairs and leaves the one unpaired number.