Algorithms Beyond the Basics in JavaScript

Glossary

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

Search the glossary

#

32-bit integer: The kind of number JavaScript converts to before running a bit operator: only 32 bits are kept, and the top bit means negative. That is why `1 << 31` is negative and masks should stay at 30 or 31 options.

A

A* (A-star): A shortest-path algorithm that speeds up a search for one goal by using a guess of the distance still left.
Adjacency list: A way to store a graph as a Map from each place to an array of its neighbors. Alex's delivery map is stored this way, with each neighbor paired with its driving minutes once the graph is weighted.
Array of arrays: A 2D table built as one array per row. The knapsack's `best` table is made this way, so best[i][t] is the cell for the first i batches and t minutes.
Autocomplete: Suggesting every stored word that starts with what the user has typed so far. Kettle & Crane's search box does this with a trie, so "ho" suggests Holiday Blend, Honey Process and the House blends.

B

Backtracking: A way to list every possible answer by building it one choice at a time: choose, explore, then undo the choice. Priya's gift-box search uses it to try combinations of items.
Base case: The simplest case in a recursive function, where it stops and returns an answer 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. It is slower than Dijkstra's algorithm, so it is used only when negative weights are possible.
BigInt: A JavaScript number type, written with an `n` after the digits (like `1n`), that can hold whole numbers of any size. It is used for `ways(100)`, which is too big for ordinary numbers, and mixes only with other BigInts.
Binary: A way of writing numbers using only 0s and 1s, where the places are worth 1, 2, 4, 8 and so on. For example `1101` means 8 + 4 + 0 + 1 = 13.
Bit: A single 0 or 1 digit in a binary number. Each bit stands for one power of two, and in a bitmask each bit can stand for one on/off option.
Bit operators: Operators that work on each column of bits in a number separately: `&` (and), `|` (or), `^` (XOR) and `~` (not). They are used to store flags in one number and to list subsets.
Bit shift: Moving every bit of a number left or right. `<<` doubles for each place, `>>` halves (rounding down and keeping the sign), and `>>>` shifts right but always fills with 0s.
Bitmask: A single number whose bits stand for on/off options, such as grind, gift wrap and express shipping on one order. Each option gets its own power of two so they don't share a bit.
Bottom-up: Dynamic programming that works out the smallest cases first and builds up to the big answer, using a table instead of recursion. The shelf count `waysTable` fills a table from length 2 up to n this way.
Brute force: A solution that tries every possibility. It is slow but easy to get right, so it is a good first version and a way to check the answers of a faster one.

C

Call stack: The place where JavaScript keeps track of the function calls in progress. Recursion that goes too deep fills it and causes a RangeError.
Choice tree: A drawing of all the choices a backtracking search can make, one level per decision. For the add-ons gift wrap, card and express, each level is a yes or no and the eight leaves are the eight answers.
Closure: A function that remembers the variables from where it was created, even after the outer function has finished. The function returned by `memoize` keeps using its own `memo` Map this way.
CommonJS: The traditional way of loading modules in Node.js, using `require(...)` instead of `import`. Files written this way need no `package.json` and run with just `node file.js`.
Comparator: A function you pass to `sort` that says which of two items goes first: a negative result puts `a` first. It is needed because a bare `sort()` compares items as text, which is wrong for numbers and arrays.
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 linked to each other, directly or through other items. In Sam's pools, each set of cafés sharing a delivery is one component.
Copy (of an array): A new array with the same items, made with `slice()`, so later changes to the original don't touch it. Backtracking saves `chosen.slice()` at the base case, because otherwise every saved answer would be the same array that keeps being emptied.
CSV (comma-separated values): A plain-text file format where each line is one record and its pieces are separated by commas, usually with a header line first. For example, a `roads.csv` file can list each road as `from,to,minutes`.
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 wait for each other forever, so no valid order exists.

D

DAG (directed acyclic graph): A graph whose edges have a direction and that contains no cycles. Jo's morning tasks form a DAG, which means at least one valid topological order exists.
Dependency: A task that must be done before another can start. Roasting depends on receiving the green beans first.
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 gets Alex to Daybreak in 29 minutes, where BFS's fewest-roads route takes longer.
Directed graph: A graph whose edges point one way, from one vertex to another. In the task graph, an edge from A to B means "A before B".
Dynamic programming: A way to solve a problem from the answers to smaller problems that repeat, saving each answer instead of recomputing it. It needs overlapping subproblems and optimal substructure, and can be done top-down or bottom-up.

E

Edge case: An input at the limits of what a function should handle, such as an empty array, one item, all items equal, duplicates or a missing target. Testing them catches bugs that ordinary examples miss.
ENOENT: The error Node throws when a file you try to read doesn't exist. In the optimizer it usually means you ran the program outside the `roaster` folder or mistyped the file name.
Error handling (throw, try/catch): `throw new Error(...)` stops a function with an error, and a `try`/`catch` block catches it so the program can print a clear message instead of crashing. It can be used, for example, to report a cycle in a set of task rules.

F

Factorial (n!): The product of all whole numbers from 1 up to n. It counts the possible orders of n items, so three cafés have 3! = 6 routes.
Flag: One on/off option stored as a single bit in a bitmask. GRIND, GIFT_WRAP and EXPRESS are flags worth 1, 2 and 4.
Floyd-Warshall: A shortest-path algorithm that finds the shortest 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 to change it. It is fast, but only right when something like a swap argument shows the choice is safe; with $10, $25 and $30 gift cards it gives the wrong answer for $50.
Greedy choice: The option that looks best right now, taken at each step of a greedy algorithm. For the cupping room, it is the booking that ends first.

I

In-degree: The number of arrows pointing into a vertex, which in a task graph is how many tasks it must wait for. `bag` has an in-degree of 2 because it waits for `blend` and `clean grinder`.
Infinity: A JavaScript value larger than every other number, and `Infinity + 1` is still `Infinity`. It is used to mean "no route or amount found yet", since it loses every comparison against a smaller value.
Interval: A stretch of time with a start and an end, stored as a `[start, end]` array of minutes since midnight. A cupping-room booking from 09:00 to 10:30 is `[540, 630]`.
Interval scheduling: Choosing the most non-overlapping intervals by sorting by end time and taking each one that fits. Priya uses it to fit the most bookings into the cupping room.

K

Kahn's algorithm: A way to produce a topological order by repeatedly taking a task whose in-degree is 0 and lowering the in-degree of the tasks after it. If the order comes out short, there is a cycle.
Knapsack (0/1 knapsack): The problem of choosing items, each taken whole or not at all, for the most total value within a limit. Jo uses it to pick which roast batches fit in her 60 minutes (and later 180).
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. It uses union-find to check this.

L

LTS (Long-Term Support): A Node.js release line that receives updates and fixes for an extended period, which makes it the safe version to install. Examples such as these need Node.js 22 LTS or newer.

M

Map: A JavaScript collection of key-value pairs that remembers insertion order, with `set`, `get`, `has` and `size`. The memo, the weighted graph and the trie's `children` are all Maps.
Memoization: Saving each answer the first time you work it out, usually in a Map, so a repeated call is just a lookup. It cuts `ways(30)` from about 2.7 million calls to 59.
Min-heap: A collection that always hands back its smallest item first, in O(log n) time for push and pop. JavaScript has none built in, so a small `MinHeap` class can be written and used for room counting, Dijkstra's algorithm and roast scheduling.
Minimum spanning tree: The cheapest set of edges that links every vertex, with no loops. For Alex's snowstorm, it is the fewest plowed minutes that keep every place reachable.

N

NaN: The special value JavaScript gives when a calculation isn't a valid number, such as adding `undefined` to a number. It appears silently, with no error, when code reads past the end of an array and does arithmetic on the result.
Negative weight: An edge that lowers the total instead of adding to it, such as a rebate on a delivery fee. It breaks Dijkstra's algorithm because a place that was already handled could still get faster.
Node.js: A program that runs JavaScript outside a web browser. A file is run with `node file.js`, and these examples need Node.js 22 LTS or newer.
node:fs: Node's built-in file-system module, loaded with `require("node:fs")`. `fs.readFileSync(path, "utf8")` reads a whole file as text, as `loadRoads` does with `roads.csv`.

O

Optimal substructure: The property that the best answer to a big problem is built from best answers to smaller ones, such as `ways(n)` from `ways(n - 1)` and `ways(n - 2)`. Along with overlapping subproblems, it is what makes dynamic programming work.
Overlap: Two intervals overlap when each one starts before the other ends. Back-to-back bookings, where one ends exactly when the next starts, do not overlap.
Overlapping subproblems: The same smaller question being asked many times inside a bigger problem. Plain recursion for `ways(30)` re-asks `ways(28)` over and over, which is what makes it slow.

P

Path compression: A union-find trick where `find` points every item it passed on the way up straight at the root, so the next walk takes one step.
Permutation: One ordering of all the items. Three cafés can be visited in 6 permutations, and n items have n! of them.
Power of two: A number such as 1, 2, 4, 8 that has exactly one 1 bit in binary. Giving each option a power of two keeps flags from sharing a bit.
Prefix: The start of a word, such as "ho" in "house". A trie finds all words that share a prefix.
Prim's algorithm: Another way to build a minimum spanning tree: grow a single tree outward from one starting place, using a heap. It gives the same kind of result as Kruskal's algorithm.
Pruning: Cutting off a branch of the search as soon as it can't lead to an answer. In the $45 gift box, `break` stops the loop once the next item pushes the total past $45.

Q

Queue: A list where items are taken from the front in the order they arrived. Kahn's algorithm keeps a queue of tasks that are ready to start.

R

RangeError: Maximum call stack size exceeded: The error JavaScript throws when recursion goes so deep that the call stack runs out of room. Bottom-up tables and Kahn's algorithm avoid it because they don't recurse.
Relaxing an edge: Lowering a place's best known time because a road through the current place gives a faster way to reach it. Dijkstra's algorithm relaxes roads and then pushes the neighbor with its new time.
Root (union-find): The one member that stands for its whole group in union-find. Two items are in the same group exactly when following their parents upward reaches the same root.

S

SameValueZero: The rule that `Map` and `Set` use to compare keys: it works like `===`, except `NaN` equals itself, and objects and arrays match only if they are the very same object. This is why an array key like `[15, 16]` can't be found again with a new array.
Set: A JavaScript collection that holds each value once, with `add`, `has` and `delete`, so checking membership is O(1). It tracks which cafés are already in a route and which corners are closed.
Shortest path: The route between two places with the smallest total weight, such as the fewest driving minutes. It can differ from the route with the fewest roads, which is what BFS finds.
Sliding window: A run of neighboring items that moves along an array one step at a time, updating a running total by adding the new item and dropping the old one. It finds the best 7 days of sales in O(n).
Slow and fast pointers: Two indexes moving the same way through one array: the fast one reads every item and the slow one marks the end of the tidy part. Sam's duplicate order IDs are removed in place this way.
Spread / rest syntax (...): In a function's parameters, `...args` collects all the arguments into an array; written in a call or an array, it spreads an array back out into separate items. `memoize` uses both.
Stable sort: A sort that keeps equal items in their original order. JavaScript's `sort` has been stable since ES2019, so equal roads keep their file order.
Stack overflow: What happens when recursion goes too deep to fit the call stack; in JavaScript it appears as `RangeError: Maximum call stack size exceeded`.
Stale entry: An old heap entry holding a slower time for a place that has since been reached faster. Dijkstra's algorithm skips it with `continue` when it pops.
Subarray: A run of items that sit next to each other in an array. Problems about the best or shortest run of days are subarray problems, and point to a sliding window.
Subset: Any selection of the items, from none to all of them. n items have 2ⁿ subsets, so the three add-ons have 8.
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 the result is no worse. For the cupping room, swapping in the booking that ends first never causes a clash.

T

Tabulation: Dynamic programming that fills a table from the smallest case up, so each bigger answer reads earlier ones, with no recursion. `fewestCards` fills one slot per dollar amount this way.
Top-down: Dynamic programming that starts with the big question, recurses down to smaller ones and saves answers with memoization.
Topological order: An order of tasks in which every task comes after everything it depends on. Jo's morning has several valid ones, since the grinder can be cleaned any time before bagging.
Trie: A tree of letters where words with the same start share the same path, and a flag marks where a word ends. It powers the autocomplete on shop.kettleandcrane.com.
Two pointers: A pattern that keeps two indexes into the same array, either starting at both ends and moving inward or moving the same way. On sorted prices it finds a pair for the $30 gift card 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 group's root, so the paths stay short.
Union-find: A structure that keeps items in groups and answers "are these two in the same group?" almost instantly through `find` and `union`. Also called disjoint set union; Sam uses it to track which cafés are in the same delivery pool.

W

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

X

XOR (exclusive or): A bit operator that gives 1 where two bits differ. Because `x ^ x` is 0, XORing a list of order IDs cancels every pair and leaves the one ID that appears only once.