Glossary

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

Search the glossary

#

0/1 knapsack: A problem where each item (such as one of Jo's roast batches) is taken whole or not at all, and you want the most value that fits within a limit like 60 minutes. It is solved with a 2D table.
2D array: An array of arrays, used as a table with rows and columns. `new int[rows][cols]` builds one filled with zeros, like the knapsack's `best` table.

A

A* (A-star): A shortest-path algorithm that searches toward a single goal, guided by an estimate of the distance still left. The estimate lets it skip many places that Dijkstra's algorithm would explore.
adjacency list: A way to store a graph as a map from each place to a list of its neighbors. In a weighted graph, each neighbor is stored as an `Edge` record that also carries the driving minutes.
ArrayDeque: A Java collection that works well as a queue, where items are added at the back and `poll` takes from the front. Kahn's algorithm uses it to hold ready tasks.
ArrayIndexOutOfBoundsException: The error Java throws when code reads or writes an array position that doesn't exist, such as index 61 in an array of length 61. Check lengths and loop bounds.
Arrays.copyOf / Arrays.toString / Arrays.fill: Helper methods from `java.util.Arrays`. `copyOf` copies the first items of an array, `toString` prints an array in brackets, and `fill` sets every slot to one value, as when the gift-card table starts at INF.
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: Building an answer one choice at a time by choosing, exploring the rest, then undoing the choice so the next one starts clean. It lists every subset or order of a small set of items.
base case: The simplest situation in a recursive method, where it stops calling itself and returns or saves a result. In `subsets` it is 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.
binary: A way of writing numbers using only 0s and 1s, where each digit (a bit) is worth 1, 2, 4, 8 and so on from the right. So `1101` is 13.
bit operators: Operators that work on each bit of a number separately: `&` and, `|` or, `^` XOR, `~` not, `<<` shift left (doubles), `>>` shift right (halves, keeps the sign), and `>>>` shift right filling with zeros.
bitmask: A single number whose bits each stand for an on/off option, such as grind, gift wrap and express on an order. Each option is called a flag, and you set, test and clear flags with `|`, `&` and `~`.
bottom-up (tabulation): Dynamic programming that fills a table starting from the smallest case, so each bigger answer just reads earlier ones. It uses a loop instead of recursion, so it avoids StackOverflowError.
brute force: Trying every possibility to find the answer. It is slow but simple, and its answers let you check a faster solution on small inputs.

C

choice tree: A drawing of all the choices a backtracking search can make, one level per decision, such as yes or no for each add-on. Each path to the end is one answer.
Comparator.comparingInt: A way to tell Java how to order objects by a number, given as a lambda like `b -> b.end()`. It is used to sort bookings and to order heaps.
compressed trie: A trie that saves memory by storing a run of single-child letters, such as "oliday blend", in one node.
computeIfAbsent: A `Map` method that computes and stores a value when a key is missing. It should not be used for recursive memoization, because the recursive call changes the map mid-update and throws `ConcurrentModificationException`; use plain `get` then `put` instead.
ConcurrentModificationException: An error Java throws when a map or list is changed while it is being updated. Calling `computeIfAbsent` with a lambda that recurses and changes the same map causes it.
connected component: A group of items that are all linked to each other, directly or through others. In union-find, each group is one connected component.
copy of a list: A new list with the same items, made with `new ArrayList<>(chosen)`. Backtracking saves a copy at the base case so later undo steps don't empty the saved answers.
CSV (comma-separated values): A plain text file where each line is a record and fields are separated by commas, such as `Roastery,Burnside,6`. The first line is often a header, which the code skips.
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 graph whose edges have a direction and that has no cycles. Only a DAG of task rules has a valid topological order.
dependency: A task that must be finished before another can start. If B can't begin until A is done, B has a dependency on A.
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 weights of zero or more.
directed graph: A graph whose edges point one way, from A to B, such as "A must happen before B". It is used to model rules like task dependencies.
dynamic programming: Solving a problem by building on answers to smaller problems that repeat. It applies when a 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 array, one item, all items equal, duplicates, or a missing target. Test these against your brute force.
edit distance: The fewest letter changes (insertions, deletions or replacements) needed to turn one word into another. It is a classic 2D dynamic programming problem.
exponential time: A running time that multiplies with every extra item, such as 2ⁿ for subsets or about 1.6ⁿ for plain recursive `ways(n)`. It is only practical for small inputs.

F

factorial (n!): The product n × (n−1) × … × 1, which counts the orderings of n items (3 items give 6). It grows even faster than 2ⁿ.
Fenwick tree: A data structure that gives fast range totals while values change, supporting quick updates and quick sums over a range. It is related to segment trees, which solve the same kind of problem.
Files.readAllLines: A Java method that reads a whole file as a list of lines. It can throw `IOException`, so the method using it declares `throws IOException`.
find (union-find): The two union-find operations: `find(x)` walks up parents to x's group root, and `union(a, b)` joins two groups, returning false if they were already one.
Floyd-Warshall: A shortest-path algorithm that finds the best route between every pair of places at once.

G

greedy algorithm: An approach 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; Kettle & Crane's gift cards break it.
greedy choice: The option that looks best right now at each step of a greedy algorithm, such as the biggest coin that fits or the booking that ends first.

H

heap (min-heap): A structure that always gives you the smallest item first; Java's version is `PriorityQueue`. It picks the nearest place in Dijkstra's algorithm and the earliest end time when counting rooms.

I

identity vs equals: Arrays are equal as map keys only if they are the very same object, so a fresh `int[]` with the same numbers is a different key. Records and Lists compare by contents, so use them as multi-part keys.
IllegalStateException: A Java exception used here to signal that the task rules contain a cycle, thrown when the topological order comes out shorter than the task list.
in-degree: The number of arrows pointing into a vertex, which is how many tasks it waits for. Tasks with an in-degree of 0 can start now.
INF (Integer.MAX_VALUE): The largest `int`, used to mean "not possible yet" in a table or distance map because it loses every smaller-than comparison. Never add to it, since it wraps to a negative number.
Integer.bitCount / toBinaryString / 0b literal: Java tools for bits: `toBinaryString` shows a number's bits, a `0b` prefix writes a number in binary, and `bitCount` counts the 1 bits.
interval: A stretch of time with a start and an end, stored as a record of minutes since midnight, such as a booking in the cupping room.
interval scheduling: Choosing the most non-overlapping bookings by sorting by end time and taking each that starts after the last one chosen ends.

J

Javadoc: Java's official online documentation pages for standard classes, which also state costs such as O(log n) for `PriorityQueue`.
JDK (Java Development Kit): The free download that lets you compile and run Java programs. With version 21 or newer, a single-file program can be run directly with `java File.java`.

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.
Kruskal's algorithm: Builds a minimum spanning tree by going through roads from shortest to longest and keeping each one that joins two places not yet connected, checked with union-find.

L

lambda: A tiny method with no name, such as `b -> b.end()`, handed to other code. Here it tells a Comparator what to sort by.
LinkedHashMap: A `HashMap` that remembers the order items were inserted, so output is the same every run.
longest common subsequence: A classic 2D dynamic programming problem that finds the longest sequence of letters appearing in the same order in two strings. The letters need not be next to each other.

M

memoization: Saving each answer in a map the first time you work it out, so a repeated call is just a lookup. Java has no `@cache`, so you keep the memo yourself.
merging intervals: Joining overlapping or touching time periods into busy periods by sorting by start time and stretching the last period's end.
method reference: A short way to pass an existing method where a lambda is expected, such as `Road::minutes` or `Integer::sum`.
minimum spanning tree: The cheapest set of edges that links every vertex, with no loops. For Alex it is the fewest plowed minutes that keep every place reachable.

N

negative weight: An edge that lowers the total, such as a fee rebate. It breaks Dijkstra's promise that roads only add time.

O

optimal substructure: A property 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 grows past what its type can hold, Java wraps around silently (a `long` tops out near 9.2 × 10¹⁸). `Math.addExact` throws `ArithmeticException` instead.
overlap: Two intervals overlap when each starts before the other ends. An interval starting exactly when another ends does not overlap it, so back-to-back bookings are fine.
overlapping subproblems: The same smaller question being asked many times, as when `ways(29)` asks for `ways(28)` again. It is what makes plain recursion slow and memoization worthwhile.

P

path compression: A union-find trick where `find` points every item it passed straight at the root, so the next walk is one step.
permutation: One order of all the items, such as one route through three cafés. n items have n! permutations.
power of two: A number like 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 trie is also called a prefix tree.
Prim's algorithm: Another way to build a minimum spanning tree, by growing a single tree outward from one start place with a heap.
PriorityQueue: Java's min-heap: `poll` always returns the smallest item by the chosen ordering. It gives the nearest place in Dijkstra and the soonest-due batch in the project.
pruning: Cutting off a branch of the search as soon as it can't lead to an answer, such as when a gift box already costs more than $45.

R

record: A short Java class that holds fixed fields, like `Pair(low, high)`, and compares by those fields. Records work well as map keys because they get `equals` and `hashCode` automatically.
relaxing an edge: In Dijkstra's algorithm, lowering a place's best known time because a road through the current place gives a faster route.
root (union-find): The one member that stands for its whole group. Two items are in the same group exactly when following parents from each reaches the same root.

S

shortest path: The route with the smallest total weight, such as the fewest minutes, which is not always the route with the fewest roads.
sign bit: The leftmost bit of an `int`: 1 means the number is negative. `>>` copies it into empty places, while `>>>` shifts in zeros.
sliding window: A run of neighboring items that moves along an array, updating a running total by adding the new item and dropping the old one. Windows can have a fixed size or grow and shrink.
slow and fast pointers: Two indexes moving the same way through an array: 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.
StackOverflowError: The error Java throws when recursion goes too deep. Bottom-up tables avoid it, and in backtracking it hints that each call isn't moving on.
stale entry: An old heap entry with a slower time for a place that was later reached faster. Dijkstra's algorithm skips it when popped.
string matching (KMP): Algorithms that find a short pattern inside a longer text quickly. KMP (Knuth-Morris-Pratt) is a well-known one that avoids rechecking letters it has already matched.
subset: Any selection of the items, from none to all. n items have 2ⁿ subsets.
swap argument: A way to prove 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 with the big question and recurses to smaller ones, saving answers with memoization.
topological order: An order of tasks in which each one comes after everything it depends on. It exists only if the rules have no cycle, and Java has no built-in version.
TreeMap: A Java map that keeps its keys sorted, so a trie node's letters come out alphabetically.
trie: A tree of letters where words with the same start share a path, each node has a map of children and an `isWord` flag. It makes lookups cost one step per letter and powers autocomplete.
two pointers: Two indexes moving through one array, from both ends or in the same direction. On a sorted array they find a pair in O(n) with no extra memory.

U

union by size: A union-find trick that hangs the smaller group's root under the bigger group's root, so paths stay short.
union-find: A structure that tracks which items are in the same group as links arrive, with fast `find` and `union`. It answers "are these two cafés in the same pool?" in nearly constant time.

V

vertex and edge: A vertex is a point in a graph, such as a place or a task; an edge is a link between two vertices, such as a road or a "before" rule. Costs like O(V + E) count them.

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. Since `x ^ x` is 0, XOR-ing an array cancels pairs and leaves the one unpaired number.