Glossary

2-node — In a 2-3 tree, a node that has two children.

3-node — In a 2-3 tree, a node that has three children.

adaptive quadrature — A technique in which a program detects areas where its approximation method may produce large errors and then refines its method in those areas.

adjacent — In a network, if two nodes are connected by a link, they are adjacent.

adversary — In cryptography, a person trying to intercept and decipher a message sent by a sender to a receiver.

algorithm — A recipe for getting something done.

ancestor — In a tree, a node's parent, its parent's parent, and so on to the root node are the node's ancestors.

array — A chunk of contiguous memory that a program can access by using indices—one index per dimension in the array.

associative array — See hash table.

asymptotic performance — The limit of an algorithm's performance as the problem size grows very large.

attacker — In cryptography, a person trying to intercept and decipher a message sent by a sender to a receiver.

augmenting path — A path through a residual capacity network that improves a maximal flow solution.

AVL tree — A sorted binary tree in which the heights of two subtrees at any given node differ by at most 1.

B-tree — A balanced tree in which internal nodes (called buckets) can hold several values and corresponding branches.

B+tree — Similar to a B-tree, except that the tree's nodes store only key values and pointers to the rest of each record's data instead of holding the data itself.

backtracking — A recursive algorithm that considers partial solutions. If it finds a partial solution that cannot be extended to a full solution, the algorithm discards the partial solution, backtracks to the previous feasible test solution, and continues searching from there.

balanced tree — A tree that rearranges its nodes as necessary to guarantee that it doesn't become too tall and thin. That allows algorithms that travel through the tree to run in O(log N) time.

Big Omega notation — An algorithm's big omega run time is Ω(g(N)) if the function g(N) is a lower bound for the algorithm's runtime function.

Big O notation — An algorithm's big O run time is O(g(N)) if the function g(N) is an upper bound for the algorithm's runtime function.

Big Theta notation — An algorithm's big theta run time is Θ(g(N)) if the function g(N) is both a lower and upper bound for the algorithm's runtime function.

binary search — A search strategy that repeatedly divides the search space into two halves and then searches the half that contains the target item.

binary tree — A tree with degree 2.

bipartite matching — The process of matching the nodes in one group of a bipartite network with the nodes in the other group.

bipartite network — A network in which the nodes can be divided into two groups, A and B, and every link connects a node in group A with a node in group B.

block cipher — A cipher in which the plaintext is broken into blocks of the same size, each block is encrypted, and the blocks are combined to give the ciphertext.

bottom-up B-tree — A B-tree that performs bucket splits as recursive calls end and move up toward the root.

branch — Connects a parent and child node in a tree.

branch and bound — A tree search algorithm in which the program moves down a branch and then decides whether it is possible to improve its current solution enough to be better than the best solution found so far. If the current solution cannot improve on the best solution so far, the algorithm stops exploring that part of the tree.

breadth-first traversal — In a tree or network, a traversal that visits all of a node's children before visiting any other nodes. This makes the traversal visit nodes close to the starting node before visiting nodes farther away.

bucket — A data structure used to hold items that are mapped into it. In a hash table, a bucket might be a linked list holding all the items mapped to the bucket. In a B-tree, a bucket is an internal node that can hold several values and corresponding branches.

byzantine generals problem — A problem in which a set of generals, some of whom may be traitors, must reach a consensus on some action. Each loyal general has a piece of information, and the loyal generals must learn the values of the other loyal generals.

Caesar substitution cipher — A substitution cipher in which each letter in the message is shifted by some amount.

capacitated network — A network in which the links have maximum capacities.

capacity — In a network, the maximum amount of something that can move through a node or link, such as the maximum current that can flow through a wire in an electric network or the maximum number of cars that can move through a link in a street network per unit of time.

cell — An object that makes up a linked list. A cell contains data and a link to the next cell in the list.

child — A child node is connected to its parent in the tree. Normally a child is drawn below its parent.

cipher — A pair of algorithms used to encrypt and decrypt messages.

ciphertext — In cryptography, a message that has been encrypted to be sent securely.

circular array — An array used to hold a queue in which you treat the last item as if it comes immediately before the first item.

circular linked list — A linked list in which the last link points back to the first item in the list.

cluster computing — Distributed computing that uses a collection of closely related computers, often on an intranet or special-purpose network.

collision — In a hash table, a collision occurs when you map a value to a position that is already occupied in the hash table.

collision-resolution policy — When a collision occurs in a hash table, a collision-resolution policy determines how the hash table handles the new value.

combination — See selection.

complete tree — A tree in which every level is completely full, except possibly the bottom level, where all the nodes are pushed as far to the left as possible.

complexity theory — See computational complexity theory.

composite number — A natural number greater than 1 that is not prime.

computational complexity theory — The related study of the difficulty of computational problems, focusing on the problems themselves rather than on specific algorithms.

connected — In an undirected network, nodes A and B are connected if node B is reachable from node A. An undirected network is connected if every node is reachable from every other node.

connected component — In a network, a set of nodes that are mutually connected.

connectivity matrix — A matrix that represents the connections between nodes in a network.

consensus problem — In distributed computing, a problem in which a number of processes must agree on a data value even if some of the processes fail.

coprime — See relatively prime.

cost — In a network, a link may have an associated cost. Less commonly, a node may have a cost.

cryptanalysis — The study of methods attackers use to break an encryption system.

cryptography — The study of methods for encrypting and decrypting messages so that a sender can transmit them securely to a receiver without an attacker's recovering the original message.

cycle — In a network, a path that returns to its starting point.

cycle detection — The process of determining whether a network contains a cycle.

data parallelism — A form of parallel processing in which emphasis is placed on distributing data among processors that execute the same or similar programs.

data structure — A way of arranging data to make solving a particular problem easier.

deadlock — In distributed computing, when two processes block each other while each waits for a mutex held by the other.

decipher — See decrypt.

decision tree — A tree that lets you model a problem as a series of decisions that leads to a solution.

decrypt — In cryptography, to convert a ciphertext message back into plaintext.

degree — For a node in a tree, the number of children the node has. For a tree, the maximum degree of any of its nodes. For a node in a network or graph, the number of links leaving the node.

depth — For a tree node, the node's level.

depth-first traversal — In a tree or network, a traversal that visits some nodes far from the starting point before visiting all the nodes closest to the starting point.

deque — Pronounced “deck.” A queue that allows you to add items to and remove items from either end of the queue.

descendant — In a tree, a node's children, their children, and so on are the node's descendants.

deterministic finite automaton (DFA) — A virtual computer that uses a set of states to keep track of what it is doing. At each step, it reads some input. Based on the input and its current state, the computer moves into a new state. One state is the initial state where the machine starts. One or more states can be marked as accepting states.

deterministic finite state machine — See deterministic finite automaton.

DFA — See deterministic finite automaton.

dictionary — A hash table maps a key to a value, so hash tables are sometimes called dictionaries.

dining philosophers problem — A problem in which N philosophers sit at a table with a fork between each pair. To eat, a philosopher must acquire both adjacent forks without talking to his neighbors.

directed — In a network, a link is directed if you can traverse it in only one direction. A network is directed if it contains only directed links.

direct recursion — Occurs when a method calls itself directly.

distributed computing — Multiple computers working together over a network to perform a task.

edge — See link.

edit distance — For two strings, the number of changes you need to make to turn the first into the second.

eight queens problem — Positioning eight queens on a chessboard so that none of the queens can attack any of the others.

embarrassingly parallel — When an algorithm naturally breaks into parallelizable pieces that require minimal communication.

encipher — See encrypt.

encrypt — In cryptography, to convert a plaintext message into ciphertext.

Euclidian algorithm — See Euclid's algorithm.

Euclid's algorithm — An algorithm for quickly finding the GCD of two numbers.

exhaustive search — Searching all possible items to find a target item. Searching every possible solution to find the best one.

external node — In a tree, a leaf node.

external sorting — Sorting data that cannot fit in memory. Data can be sorted on disk files or tape drives.

factorial — The factorial of a number n, written n! and pronounced “n factorial,” equals n × (n − 1) × (n − 2) ×...×1.

fair — A pseudorandom number generator is fair if it produces all its possible outputs with the same probability. A PRNG that is not fair is called biased.

Fermat liar — If p is not prime and the value n with 1 ≤ n ≤ p satisfies the equation n^p–1 Mod p = 1, n is called a Fermat liar because it incorrectly implies that p is prime.

Fermat witness — If p and n are natural numbers where 1 ≤ n ≤ p and n^p–1 Mod p ≠ 1, n is called a Fermat witness because it proves that p is not prime.

Fibonacci numbers — The Fibonacci numbers are defined by Fibonacci(0) = 0, Fibonacci(1) = 1, and Fibonacci(n) = Fibonacci(n − 1) + Fibonacci(n − 2) for n > 1.

FIFO — See queue.

FIFO list — See queue.

fill percentage — For a hash table, the percentage of the data structure that is filled. Hash tables with high fill percentages may result in reduced performance.

first common ancestor — For any two nodes, the node that is the ancestor of both nodes that is closest to the nodes.

flops — Also spelled FLOPS. Floating-point operations per second. Calculation speeds are sometimes measured in megaflops, gigaflops, teraflops (one trillion flops), or petaflops (1,000 teraflops).

Floyd's cycle-finding algorithm — See tortoise-and-hare algorithm.

Ford-Fulkerson algorithm — An algorithm for calculating maximal flows in a network.

four-coloring theorem — A theorem that states that any map can be colored with at most four colors.

full tree — A tree in which every node has either zero children or as many children as the tree's degree.

gasket — A type of self-similar fractal in which you start with a geometric shape such as a square or triangle, divide the shape into smaller similar shapes, and then recursively fill some, but not all, of the smaller shapes.

GCD — See greatest common divisor.

general and lieutenants problem — A problem in which a general gives an order to his lieutenants, but the general or some lieutenants might be traitors. The goal is for the loyal lieutenants to decide on a common action. If the general is not a traitor, that action must be the one the general ordered.

generator — In one type of self-similar fractal curve, an initiator sets the fractal's basic shape. At each level of recursion, some or all of the initiator is replaced with a generator curve.

graph — A network.

greatest common divisor (GCD) — The largest integer that divides two integers evenly.

grid computing — Distributed computing that uses a collection of loosely related computers that may communicate over a public network. A grid may include different kinds of computers running different operating systems.

hashing — The process of mapping a key to a location in a hash table.

hash table — A data structure and algorithms that map data to locations in the data structure.

heap — A complete binary tree in which every node holds a value that is at least as large as the values in all its children.

height — For a node in a tree, the length of the longest path from the node downward through the tree to a leaf node. For a tree, this is the same as the root's height.

heuristic — An algorithm that often produces a good result but that is not guaranteed to produce the best possible result.

Hilbert curve — A space-filling fractal curve created by starting with an initiator curve and then recursively replacing pieces of the initiator with a suitably scaled, rotated, and translated generator curve.

hill climbing — A heuristic strategy that at each step takes the action that moves the algorithm closest to the best possible solution. This is similar to a hiker trying to find the top of a mountain at night by always moving uphill.

in-degree — In a directed network, the number of links entering a node.

indirect recursion — Occurs when a method calls itself indirectly by calling another method that then calls the first method.

initiator — A curve that sets the basic shape for one type of fractal. At each level of recursion, some or all of the initiator is replaced with a generator curve.

inorder traversal — In a tree or network, a traversal that visits a node's left child, and then the node, and then the node's right child.

internal node — A tree node that has at least one child.

key — In cryptography, a piece of information that allows the recipient of an encrypted message to decode the message. In modern cryptography, it is assumed that the attacker knows the encryption method, so an attacker who has the key can also decrypt the message.

knight's tour problem — A knight visits every position on a chessboard without visiting any square twice. In a closed tour, the final position is one move away from the starting position. A tour that is not closed is open.

Koch curve — A self-similar fractal created by starting with an initiator curve and then recursively replacing pieces of the initiator with a suitably scaled, rotated, and translated generator curve.

leaf node — A tree node with no children.

least common ancestor — See first common ancestor.

level — A tree node's level is the distance between it and the root node.

LIFO — See stack.

LIFO list — See stack.

linear array — A one-dimensional array.

linear congruential generator — A pseudorandom number generator that uses a simple recurrence relation to generate numbers.

linear probing — A technique used to build a hash table in which the collision-resolution policy adds a constant number, usually 1, to each location that is already occupied to generate a probe sequence.

linear search — To search linearly through a linear array or other linear data structure for a value.

link — A reference or pointer from one linked list cell to another, or from one node to another in a tree or network.

linked list — A list built of cells connected by one or more links.

livelock — In distributed processing, a situation similar to a deadlock in which processes are not blocked but still cannot get any work done because of how they try to get access to resources.

loop — In a network, a cycle.

minimal spanning tree — A spanning tree that has the least possible total cost in the network.

Monte Carlo integration — A numeric integration technique in which a program picks a large number of pseudorandom points and uses the fraction of those that lie within a shape to estimate the shape's area.

Monte Carlo simulation — A probabilistic technique in which the program picks pseudorandom values and determines what percentage satisfies some criterion to estimate the total number of values that satisfy the criterion.

Moore's Law — The trend noticed by Gordon E. Moore in 1965 that the number of transistors on integrated circuits doubles roughly every two years.

multiple recursion — Occurs when a method calls itself more than once.

mutex — A method of ensuring that only one process can perform an operation at a time. (The name comes from “mutual exclusion”.)

natural number — An integer greater than 0.

Newton-Cotes formulas — A numeric integration technique that uses polynomials to approximate a curve to find the area beneath it.

Newton-Raphson method — See Newton's method.

Newton's method — A method of finding the roots of a function.

NFA — See nondeterministic finite automaton.

node — An object that holds data in a tree or network. Nodes are connected by branches in trees, or links or edges in networks and graphs.

node merge — The process of merging two nodes when rebalancing a 2-3 tree.

node split — The process of splitting a node into two nodes when adding a new value to a balanced tree.

nondeterministic finite automaton (NFA) — Similar to a DFA, except that multiple links may leave a state for the same input. You can think of an NFA as simultaneously being in every possible state for its inputs.

NP — The set of problems that can be solved by a nondeterministic computer in polynomial time.

NP-complete — A problem is NP-complete if every problem in NP can be reduced to it in polynomial time.

numeric integration — The process of approximating the area under a curve numerically when you can't use the curve's antiderivative and calculus to calculate the area exactly.

numeric quadrature — See numeric integration.

octtree — A tree data structure used to locate objects in three-dimensional space.

one-time pad cipher — A cipher in which each letter in the message is combined with the corresponding letter in a pad of random letters or offsets. This is similar to a Vigenère cipher, in which the key length is the same as the message.

open addressing — A method for building hash tables in which keys are mapped into entries in an array. Different versions of open addressing use different hashing functions and collision-resolution policies.

optimization problem — A problem that asks you to find the optimal solution to a particular problem. Optimization problems often have approximate solutions.

order — In a B-tree of order K, the internal nodes hold between K and 2 × K values and have between K + 1 and 2 × K + 1 branches.

ordered tree — A tree in which the ordering of each node's children matters.

out-degree — In a directed network, the number of links leaving a node.

P — The set of problems that can be solved by a deterministic computer in polynomial time.

parent node — A node in a tree that has child nodes connected to it by branches. In a tree, every node except the root has exactly one parent.

partial ordering — A set of dependencies that defines an ordering relationship for some but not necessarily all the objects in a set.

path — In a network, an alternating series of nodes and links that leads from one node to another. If there is only one link from any node to an adjacent node, you can specify a path by listing the nodes or links it includes.

perfect tree — A full tree in which all the leaves are at the same level.

permutation — An ordered subset of items taken from a set.

plaintext — In cryptography, the message to be sent securely.

planar — A network is planar if you can draw it on a plane with none of the links intersecting.

polynomial run time — An algorithm has polynomial run time if its run time involves any polynomial involving N. O(N), O(N²), O(N⁶), and even O(N⁴⁰⁰⁰) are all polynomial run times.

postorder traversal — In a tree or network, a traversal that visits a node's left child, and then its right child, and then the node.

prefix tree — See trie.

preorder traversal — In a tree or network, a traversal that visits a node, and then its left child, and then its right child.

primary clustering — In a hash table that uses open addressing, an effect in which values that map to a cluster of entries end up extending the cluster to form long blocks of occupied entries. That increases average probe sequence length.

prime number — A natural number greater than 1 whose only factors are 1 and itself.

PRNG — See pseudorandom number generator.

probabilistic algorithm — An algorithm that produces a correct result with a certain probability.

probe sequence — The sequence of locations that an open addressing hash table algorithm tries for a value.

pseudorandom number generator (PRNG) — A number generator that uses calculations to produce numbers that seem random but that are predictable.

public-key encryption — An encryption method that uses two keys—a private key and a public key. The sender uses the public key to encrypt messages, and the receiver uses the private key to decrypt them.

pushdown stack — See stack.

quadrature — See numeric integration.

quadtree — A tree data structure that helps locate objects in two-dimensional space.

quantum computer — A computer that uses quantum effects such as entanglement and superposition to manipulate data.

queue — A data structure in which items are added and removed in first-in-first-out order.

race condition — A situation in distributed processing, particularly when a single computer has multiple CPUs, in which two processes try to write to a resource at almost the same time, and the process that writes to the resource second wins.

random solution search — A heuristic for finding a solution to a problem by randomly searching its decision tree.

reachable node — In a network, node B is reachable from node A if there is a path from node A to node B.

receiver — In cryptography, the person trying to receive a message sent by a sender.

rectangle rule — A numeric integration technique that uses rectangles to approximate the area below a curve.

recursion — Occurs when a method calls itself either directly or indirectly.

regular expression — A pattern for matching the characters in a string.

relatively prime — Two integers are relatively prime if their greatest common divisor is 1.

residual capacity — The extra flow you could add to the link in a capacitated network.

residual capacity network — A network consisting of links and backlinks marked with their residual capacities.

root — For an equation y = f(x), the equation's roots are the values of x for which f(x) = 0.

root node — The unique node at the top of the tree that has no parent.

root split — When a series of node splits cascades up a balanced tree until the root node is split.

secondary clustering — In a hash table that uses open addressing with quadratic probing, an effect in which values that map to the same address follow the same probe sequence and produce a long probe sequence.

selection — An unordered subset of a set of objects.

self-similar fractal — A curve in which pieces of the curve resemble the curve as a whole.

sender — In cryptography, the person trying to securely send a message to a receiver.

sentinel — A cell that is part of the linked list but that doesn't contain any meaningful data placed at either end of the list. It is used only as a placeholder so that algorithms can refer to a cell before the first cell or after the last cell.

shortest-path tree — A spanning tree that gives shortest paths from its root node to every other node in the network.

sibling nodes — Two nodes in a tree that have the same parent are siblings.

Sierpiski Curve — A space-filling fractal curve created by starting with an initiator curve and then recursively replacing pieces of the initiator with a suitably scaled, rotated, and translated generator curve.

Simpson's rule — A numeric integration technique that uses polynomials of degree 2 to approximate the area below a curve.

simulated annealing — A solution improvement heuristic that initially makes large changes to a solution and then over time makes smaller and smaller changes to try to improve the solution.

single recursion — Occurs when a method calls itself exactly once.

sorted tree — A tree in which the nodes are arranged so that they are processed in sorted order by a particular traversal, usually an inorder traversal.

spanning tree — A tree consisting of a network's nodes and links that connects every node in the network.

sparse array — An array data structure that contains very few entries that don't have a default value.

stack — A data structure in which items are added and removed in last-in-first-out order.

state transition diagram — A network representing a DFA's or FNA's state transitions.

stride — In a hash table with open addressing and linear probing, the stride is the value added to each location in a value's probe sequence.

strongly connected — A directed network is strongly connected if every node is reachable from every other node.

substitution cipher — A cipher in which the letters in the plaintext are replaced with other letters. Caesar substitution and the Vigenère cipher are two examples.

subtree — A node and all its descendants in a tree form a subtree.

symmetrically threaded tree — A tree that contains threads forwards and backwards through the tree's inorder traversal.

symmetric-key encryption — An encryption method that uses one key to encrypt and decrypt messages. Both the sender and receiver must have the key.

symmetric traversal — See inorder traversal.

systolic array — An array of data processing units (DPUs) called cells that use data parallelism to provide parallel processing.

task parallelism — A form of parallel processing in which emphasis is placed on distributing tasks among processors.

thread — A sequence of links that forms a path through a data structure such as a tree or network.

threaded tree — A tree that contains one or more threads.

top-down B-tree — A B-tree that performs bucket splits whenever possible as it moves down into the tree, looking for a location to place a new value.

topological sorting — The process of extending a partial ordering to a full ordering on a network.

tortoise-and-hare algorithm — An algorithm for detecting and removing a loop from a linked list. (See the section “Tortoise and Hare” in Chapter 3.)

tower of Hanoi — A puzzle in which the goal is to move a stack of disks from one peg to another by moving one disk at a time and never placing a larger disk on a smaller one.

transposition cipher — A cipher in which the plaintext's letters are rearranged in a specific way to create the ciphertext.

trapezoid rule — A numeric integration technique that uses trapezoids to approximate the area below a curve.

traversal — To visit all the nodes in a tree or network in some order and do something to them.

treesort — A sorting algorithm in which you first build a sorted tree and then use an inorder traversal to produce the sorted items.

triangular array — A two-dimensional array in which the values above the diagonal (where the item's column is greater than its row) have some default value, such as 0, null, or blank.

trie — A tree in which nodes represent letters in strings, and the path from the root to a node defines a prefix that all the strings below the node share.

TRNG — See true random-number generator.

true random-number generator (TRNG) — A number generator that uses a source of true randomness, such as radioactive decay or atmospheric noise, to produce truly unpredictable numbers.

Turing machine — A hypothetical computer that manipulates the symbols on a strip of input tape according to a simple table of rules.

two generals problem — A problem in which two generals have armies encamped just outside an enemy city, at opposite ends of town. Using messengers that might be captured by the enemy, the generals must coordinate an attack.

undirected — In a network, a link is undirected if you can traverse it in either direction. A network is undirected if it contains only undirected links.

vertex — See node.

Vigenère cipher — A substitution cipher in which each letter in the message is shifted by an amount determined by a corresponding letter in the key.

weakly connected — A directed network is weakly connected if every node is reachable from every other node when you replace the directed links with undirected links.

weight — In a network, cost.

work assignment problem — Given N people with certain skills and M jobs that require someone with certain skills, the work assignment problem is to find the best assignment of people to jobs to maximize the number of jobs that can be performed.