Glossary

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

Search the glossary

#

&^ (and not): A Go operator that keeps a's bits except where b has a 1. It is how you turn a flag off, for example `options &^ grind`.
0/1 knapsack: A problem where each item is taken whole or not at all, and you want the most total value that fits within a limit. Jo uses it to choose roast batches worth the most dollars in her minutes of roaster time.

A

A* (A-star): A shortest-path algorithm that searches toward a single goal, guided by an estimate of how far is left. The estimate lets it skip much of the map that Dijkstra's algorithm would explore.
Adjacency list: A way to store a graph as a map from each place to a slice of its neighbors. In a weighted graph, each neighbor entry also carries the road's driving minutes.
Amortized: An average cost over many operations. Appending to a slice is occasionally slow when it must grow, but averages O(1) per append.
Autocomplete: Suggesting every stored word that starts with the text typed so far, like Kettle & Crane's search box suggesting products after "ho".

B

Backtracking: Building answers one choice at a time: make a choice, explore the rest, then undo the choice so the next one starts clean. It lists every combination or order of a few items.
Base case: The simplest situation in a recursive function, answered directly without another call. 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. It is slower than Dijkstra's algorithm.
BFS (breadth-first search): A graph search that visits places in order of how many roads they are from the start. It finds the route with the fewest roads, not the fewest minutes.
Big-O: A way to describe how a program's time or memory grows with input size n. O(n) grows in step with n, while O(n²) grows with its square.
Binary: Writing numbers using only 0s and 1s, each digit being a bit. From the right, bits are worth 1, 2, 4, 8 and so on, so 1101 is 13.
Bit operators: Go operators (`&`, `|`, `^`, `&^`, `<<`, `>>`) that work on each column of bits separately. They let you test, set, clear and shift bits.
Bitmask: A number whose individual bits stand for on/off options. One order can hold grind, gift wrap and express in a single number.
bits.OnesCount: A function from Go's `math/bits` package that counts the 1 bits in an unsigned number. Use it to count how many options an order has.
Bottom-up: Dynamic programming that fills a table from the smallest case upward, so each bigger answer reads earlier ones. It uses no recursion.
Brute force: Trying every possibility. It is slow but easy to get right, so it gives answers to check a faster version against.

C

Capacity and weights: In the knapsack, the weights are what each item costs (minutes) and the capacity is the limit (minutes available). The table has one column for each amount from 0 to capacity.
Choice tree: All the choices a backtracking search can make, drawn level by level. Each path to the end is one answer.
cmp.Compare: A Go function that returns a negative number, zero or a positive number depending on how two values order. It is used inside sort functions.
Comma-ok: A Go form like `value, ok := m[key]` where `ok` says whether the key was in the map. It tells a stored 0 from a missing key.
Comparable map keys: Map keys must be comparable with `==`: numbers, strings, bools, arrays and structs work, but slices don't. To key by two numbers, use a `[2]int` array or a small struct.
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.
container/heap: Go's standard heap package. You give it a type with five methods (`Len`, `Less`, `Swap`, `Push`, `Pop`) and call `heap.Push` and `heap.Pop` to keep the smallest item first.
Copy (of a slice): `slices.Clone(chosen)` makes a new slice with the same items in a new array. Later changes to the original don't touch it, which is why backtracking saves a copy.
CSV (comma-separated values): A text file format with one record per line and values split by commas, such as `roads.csv`. Go's `encoding/csv` package reads it into slices of text.
Cycle: A path in a directed graph that leads back to where it started. Tasks on a cycle wait for each other forever, so they have no valid order.

D

DAG (directed acyclic graph): A directed graph with no cycles. Only a DAG of task rules has a topological order.
Decorator: In some languages, a function that wraps yours to add behavior such as a memo. Go has none, so you write the memo map yourself.
defer: A Go keyword that runs a call when the surrounding function returns, however it returns. It is used to close files.
Dependency: A task that must finish before another can start. Roasting depends on receiving beans.
DFS (depth-first search): A graph or tree search that follows one path as far as it can before backing up. Backtracking walks its choice tree this way.
Dijkstra's algorithm: Finds the fastest route from a start to every place 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 have a direction, like "roast before rest", so an edge from A to B does not imply one from B to A. It is used to store ordering rules between tasks.
Dynamic programming: Solving a problem by building on answers to smaller overlapping problems that are each worked out once. It works either top-down with a memo or bottom-up with a table.

E

Edge case: An input at the limits, such as an empty slice, one item, duplicates or a missing target. Test these against your brute force.
Edit distance: The fewest single-letter changes (insertions, deletions or replacements) needed to turn one word into another. It is a classic dynamic programming problem solved with a 2D table.

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 compact tree-like structure, stored in a slice, that gives fast range totals while values are being updated. Both queries and updates take O(log n) time.
Flag: One on/off option stored as its own bit, such as `giftWrap = 2`. Several flags live together in a bitmask.
Floyd-Warshall: A shortest-path algorithm that finds the best route between every pair of places at once.
Function value: A function written inline and passed to another function, such as the comparison function given to `slices.SortFunc`.

G

go run / go vet: Go commands: `go run file.go` compiles and runs a file, and `go vet file.go` checks it for suspicious code.
Greedy algorithm: Takes the best-looking choice at each step and never undoes it. It is fast but only right 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.

I

In place: Changing a slice directly instead of building a new one. `removeDuplicates` tidies the caller's slice this way.
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 (infinity constant): A big constant, `1 << 60`, meaning "not possible yet" or "no route found". It loses every comparison and is safe to add 1 to, unlike `math.MaxInt`.
Integer overflow: When a result is too big for an `int`'s 64 bits, Go wraps it around, often to a negative number, with no warning. `waysTable(92)` shows it.
Interval: A stretch of time with a start and an end, stored as a struct, here in minutes since midnight.
Interval scheduling: Choosing the most bookings that don't overlap. The greedy rule is to sort by end time and take each booking 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. A short result means a cycle.
KMP (Knuth-Morris-Pratt): A fast string-matching algorithm that finds a pattern inside a longer text in O(n + m) time. It avoids rechecking letters by using a table built from the pattern itself.
Kruskal's algorithm: Builds a minimum spanning tree by going through edges from shortest to longest, keeping each one that joins two not-yet-connected places. It uses union-find to check.

L

Longest common subsequence: The longest sequence of items that appears in the same order, though not necessarily side by side, in two inputs. It is a classic dynamic programming problem solved with a 2D table.

M

Memo map: A map from a call's inputs to its saved answer. Go has no built-in cache, so you write it by hand, often as a package-level variable.
Memoization: Saving each answer the first time it is worked out so a repeated call is just a lookup. It turns `ways(30)` from 2.7 million calls into 59.
Min-heap: A structure that always hands back its smallest item first, in O(log n) per push or pop. Dijkstra's algorithm and the room counter use one.
Minimum spanning tree: The cheapest set of edges that links every vertex, with no loops. Alex uses one to pick the fewest plowed road minutes.

N

Negative weight: An edge that lowers the total, such as a rebate. It breaks Dijkstra's promise that roads only add time.
Nil map: A map declared with `var` but never made. Reading it works, but writing to it panics, so create it with `make` or `map[K]V{}`.

O

Optimal substructure: The best answer to a big problem is built from the 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 do not overlap.
Overlapping subproblems: The same smaller question asked many times, like `ways(28)` inside both `ways(29)` and `ways(30)`. Memoization removes the repeated work.

P

Package-level variable: A variable declared outside any function, so every function in the package shares it. It can hold something like a memo map without passing it as an argument.
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! orders, like the six ways Alex could visit three cafés.
Pointer receiver: A Go method declared on `*Type` so it can change the struct itself. Heap `Push`/`Pop` and union-find methods need it.
Power of two: 1, 2, 4, 8…: a number with exactly one 1 bit. `n&(n-1) == 0` spots one, and flags use them so each option has its own bit.
Prefix: The start of a word, such as "ho" in "house".
Prim's algorithm: Another way to build a minimum spanning tree: grow one tree from a start place, using a heap.
Pruning: Cutting off a branch of a backtracking search as soon as it can't lead to an answer. In the $45 gift box, sorting lets `break` skip every later item once the total passes $45.

Q

Queue: A line where items leave from the front in the order they arrived. In Go it is a slice: `append` at the back and `ready[1:]` drops the front.

R

Relaxing an edge: Updating a place's best known time when a road gives a faster way there. It is the core step of Dijkstra's algorithm.
Root (union-find): The one member that stands for its whole group. Two items are in the same group when following parents reaches the same root.
Route rebuilding (cameFrom): Recording where each answer came from so you can recover the actual route or choice, not just its total. Dijkstra follows `cameFrom` back from the goal, and the knapsack walks back up its table rows.
rune: Go's type for one character. Ranging over a string gives runes, so a trie's children map is keyed by `rune`.

S

Shared array (slices): A slice and its copies point at the same underlying array, so a change through one can show up in another. This is why functions can change a caller's slice and why backtracking must save a clone.
Shift left / shift right: `a << n` moves bits left, doubling the number n times, and `a >> n` moves them right, halving it. `1 << n` is 2ⁿ.
Shortest path: The route with the smallest total weight, such as fewest minutes. It is not always the route with the fewest roads.
Slice of slices: A table with one slice per row, each row made with its own `make`. The knapsack table is built this way.
slices.SortFunc: A Go function that sorts a slice in place using a comparison function you supply. Sort a `slices.Clone` copy so the caller's order doesn't change.
Sliding window: A run of neighboring items that moves along a slice, updating a running total by adding the new item and dropping the old. It can have a fixed size or grow and shrink.
Slow and fast pointers: Two indexes moving the same way: `fast` reads every item and `slow` marks the end of the tidy part. They remove duplicates in place.
Stack overflow: A crash when recursion goes too deep or never ends. Go's stack grows to 1 GB first, so thousands of levels are fine but endless ones are not.
Stale entry: An old heap entry with a slower time than `dist` now holds. Dijkstra's algorithm skips it when popped.
Subset: Any selection of the items, from none to all. n items have 2ⁿ subsets.
Swap argument: A way to show greedy 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, recurses down to small ones, and saves answers with memoization.
Topological order: An order of tasks in which every "A before B" rule is kept. There can be more than one valid order.
Trie: A tree of letters where words with the same start share the same path. Each node has a `children` map and an `isWord` flag, and lookups cost one step per letter.
Two pointers: Two indexes into one slice. Walking from both ends of a sorted slice finds a pair in O(n) with O(1) memory.

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 an item's root and `union` to join two groups. With both tricks each call is nearly O(1).
Unsigned integer (uint): A whole-number type that can't be negative. `bits.OnesCount` takes a `uint`, so convert first with `uint(options)`.

V

Vertex and edge: The points (like tasks or places) and the connections between them in a graph.

W

Weighted graph: A graph whose edges carry numbers, such as driving minutes on each road.

X

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