C
Glossary
C.1 The Nature of Jargon
In the next section, the numbers in parentheses indicate the chapter or chapters
in which these terms are used and/or defined. In some instances, the reader is also
directed to the Jargon File found online (search on the term “jargon file”).
The usual notion of a definition is that a definition should read, “An X is a Y
that has properties Z,” where X is the term to be defined, Y is a larger class to
which X belongs, and Z is what distinguishes X from other members in the larger
class Y. For example, in the definition “A tree is a connected graph with no cycles,”
we have X = “tree,” Y = “connected graph,” and Z = “with no cycles.”
Unfortunately, there are many important terms in computing that cannot be
defined using the classical notion of a definition. In many instances, this is because
the term is defined as a phenomenon that has been observed to exist or because the
term has come to more or less describe a common feature. Rather than forcing the
issue with an artificial definition, we have usually avoided trying to create a true
“definition” for such terms.
C.2 Terms Used in This Book
• 3n + 1 problem (8): The 3n + 1 problem, also called the Syracuse problem or
the Collatz problem, is this: Begin with any integer n and recursively apply the
following transformation. If n is even, then divide n by 2 to produce n
= n/2.
If n is odd, then multiply n by 3 and add 1 to produce n
=3n + 1. Repeat. The
problem is to determine whether repeated applications of this transformation
eventually reduce to n
=1. All n ever tested have reduced to 1, and it is
conjectured that the repetition of this transformation will reduce any integer
n to 1, but this has not yet been proved.
• f(x)=o(g(x))(6): See asymptotic notation.
• f(x)=O(g(x))(6): See asymptotic notation.
• f(x)=Ω(g(x))(6): See asymptotic notation.
347
348 APPENDIX CGLOSSARY
• f(x)=Ω
K
(g(x))(6): See asymptotic notation.
• f(x)=Θ(g(x))(6): See asymptotic notation.
• Ackermann function (8): There are several functions that go by the name of
the Ackermann function. The one most commonly used in computer science is
the function A(m, n) defined using recursion as follows.
A(m, n)=n +1 if m =0
= A(m − 1, 1) if m>0andn =0
= A(m − 1,A(m, n − 1)) if m>0andn>0
• adjacency matrix (13): An adjacency matrix for a graph is a matrix of 0 and
1 values. Rows and columns correspond to the nodes in a graph, and 1 in the
row-i, column-j position indicates that an edge (a directed edge in the case
of a directed graph) exists from the ith node to the jth node. In the case of
undirected graphs, this is always a symmetric matrix.
• adjacent node (9): A node v
1
in a (directed) graph is adjacent to another node
v
2
in the graph if there is an edge (directed in the case of directed graphs) that
connects v
1
to v
2
.
• analysis of algorithms (6): Analysis of algorithms is the subdiscipline of com-
puter science that deals with the determination of the theoretical asymptotic
running time of a particular algorithm. For example, it can be shown by analysis
that a mergesort on N data items can always be done using at most O(N lg N)
comparisons of different items.
• ancestor of a node (10): An ancestor of a given node in a graph is any node
that can be reached from the given node by tracing upward through the parent
links, just as one’s own ancestors can be traced through parents, grandparents,
and so forth. See child node, parent node.
• arc (7, 9, 13): See graph.
• associative search (12): We say that an associative search is performed when (at
some conceptual level) a sought-for data item is found simply by associating
the key to the data item, rather than conducting a search through the data
and a comparison of the keys in the data to the key being searched for. If a
programmer is using packages like the JCF, then the package may provide the
illusion to the programmer of an associative search by a method that returns a
data item corresponding to a key, but the underlying code in the package will
necessitate a more expensive search operation.
• asymptotic analysis (3): The asymptotic analysis of an algorithm or program is
done by determining the main growth term, in the expression for the running
time cost of the algorithm or program, that dominates the running time cost
as the size of the problem being solved goes to infinity.
C.2 Terms Used in This Book 349
• asymptotic notation (6): The asymptotic notation that is used to express asymp-
totic running times of algorithms is as follows:
1. big Oh: We write f(x)=O(g(x)) if there exist constants c and C such that
x>c =⇒|f(x)|≤C ·g(x).
2. big Omega (traditional): We write f(x)=Ω(g(x)) if f(x)isnot o(g(x)),
that is, if there exists a sequence x
1
,x
2
,...,x
n
,...,tending to ∞, such that
for any fixed constant C, there exists a constant c such that x
i
>c =⇒
|f(x
i
)|≥C ·g(x
i
).
3. big Omega (Knuth’s version): We write f(x)=Ω
K
(g(x)) if for any fixed
constant C there exists a constant c such that x>c =⇒|f(x)|≥C ·g(x).
(The difference between the two versions of Omega is that in Knuth’s version
the inequality is required to hold for all values of x greater than c, and not
just for infinitely many x
i
in a sequence going off to infinity.)
4. big Theta: We write f(x)=Θ(g(x)) if there exist constants c, C
1
,andC
2
such that for all x>c we have C
1
· g(x) ≤|f(x)|≤C
2
· g(x). There is a
“little theta” that is used in asymptotic analysis, but it is beyond the scope
of this book.
5. little oh: We write f(x)=o(g(x)) if lim
x→∞
|f(x)|
|g(x)|
=0.
• average-case behavior (1, 6, 11): The average-case behavior of an algorithm is
the behavior that leads to the average-case running time. For example, the
average-case behavior of insertionsort into increasing order is that an element
will have to be pulled halfway through the existing array before its proper
location is determined. Average-case behavior usually involves probabilistic
analysis. In the insertionsort example, for any new element that should be posi-
tioned at location i in an array of length N, there is an equally likely element
that should be positioned at location N − i, and the average of i comparisons
and N −i comparisons is
1
2
N. See best-case behavior, worst-case behavior.
• average-case running time (1, 6, 11): The average-case running time of an algo-
rithm is the running time of the algorithm under the average-case conditions.
See best-case running time, worst-case running time.
• balanced tree (10): A tree is said to be a balanced tree if from any node in the
tree the split into child subtrees is a split into subtrees of approximately equal
size. Since almost no trees will be perfectly balanced, it is rarely the case that
this term is used in a precise sense. Rather, a tree will be said to be balanced if
the split into subtrees is close enough to subtrees of equal sizes for an algorithm
to run with reasonable efficiency.
• best-case behavior (1, 11): The best-case behavior of an algorithm is the behav-
ior that leads to the best-case running time. For example, the best-case behavior
of insertionsort into increasing order is that an element to be inserted belongs
exactly at the end of the list, and thus that only one comparison, with the last
350 APPENDIX CGLOSSARY
element in the current list, is needed. See average-case behavior, worst-case
behavior.
• best-case running time (1, 11): The best-case running time of an algorithm is the
running time of the algorithm under the best-case conditions. See average-case
running time, worst-case running time.
• big Oh (6): See asymptotic notation.
• big Omega (6): See asymptotic notation.
• big Theta (6): See asymptotic notation.
• binary logarithm (6): The binary logarithm of a quantity x is the logarithm
base 2 of x:log
2
x. This is usually written lg x in computer science. Binary
logarithms are more often used in computer science than other logarithms due
to the ubiquitous presence of divide-and-conquer algorithms and heuristics,
which repeatedly split problems in half in order to arrive at a solution. See
common logarithm, natural logarithm.
• binary search (3, 8): Binary search is a computational search process in which
the size of the space to be searched is cut in half repeatedly, a determination
is made as to which half of the search space holds “the answer” to be found,
and then the search is made recursively on that half of the space containing
the answer.
• binary search tree (12): A binary search tree is a binary tree whose nodes hold
key values for which the following two properties hold:
1. For any given node v, the key values for all nodes in the left subtree of v
are less than or equal to the value of the key for v.
2. For any given node v, the key values for all nodes in the right subtree of v
are greater than or equal to the value of the key for v.
• binary tree (7, 10): A binary tree is a tree in which no node has more than two
children, which are referred to as the left child and the right child.
• Boolean satisfiability (13): A Boolean satisfiability problem is the problem of
determining, for a boolean expression in some number of variables, whether
there is some assignment of true and false to the variables that will result in
the boolean expression’s evaluating to true.
• breadth-first search, breadth-first traversal (10): When a tree is visualized in
standard form, with the root node at the top and the tree descending from
the root, a breadth-first traversal is accomplished by visiting first the root,
then all the children of the root, usually in left-to-right order, then all the
children of all the children of the root, usually in left-to-right order, and so
forth. Equivalently, it is a traversal of the root node at depth 0, then the nodes
at depth 1, then the nodes at depth 2, and so forth. See depth-first traversal,
depth of a node, height of a node, inorder traversal, postorder traversal, preorder
traversal.
• bubblesort (3, 11): A bubblesort is an in-place sorting algorithm in which
N items are sorted by running N loops, the first of which positions the
C.2 Terms Used in This Book 351
largest (or smallest) element in the proper location by comparing it against
all elements, the second loop of which positions the second largest by com-
paring it against the N − 1 remaining unpositioned elements, and so forth.
See asymptotic notation, heapsort, in-place algorithm, insertionsort, mergesort,
out-of-place algorithm, quicksort.
• bucketsort (11): A bucketsort is a sorting algorithm in which N buckets are
established for items whose key value is in the range 1 through N,andas
elements are examined they are placed in the corresponding bucket.
• bush factor (10): In a tree such as a game or search tree, a node is said to have
a bush factor of k if there are k possible child paths leading from that node. All
nodes in a binary search tree, for example, will have a bush factor of 0, 1, or 2.
• child node (7, 10): When a tree is visualized in standard form, with the root
node at the top and the tree descending from the root, a child of a given node
is a node connected to the given node by a downward arc. See parent node.
• class NP (13): See NP-complete problem.
• class P (13): See NP-complete problem.
• clique (9, 13): A clique C in a graph G is a subgraph of G in which each node
in C is connected by an arc to every other node in C. See maximal clique.
• Collatz problem (8): See 3n +1problem.
• collection (5), collection classes (4): In Java, a collection is an aggregate of
multiple instances of objects. Often these objects are of the same data type,
but since all objects are instances of the Java Object class, a collection can
be formed of instances of Object type and thus have no further limitation or
specification. See JCF.
• combinatorially explosive (1): A computation is said to be combinatorially
explosive if the asymptotic running time grows as an exponential or factorial of
the number of items of data. If a search tree for a game, for example, has a fixed
number k of possible subtrees of any given node, then the running time for the
search has a combinatorially explosive running time, since there is 1 root node
at depth 0, k nodes at depth 1, k
2
nodes at depth 2, k
3
at depth 3, and so
forth, and thus k
n
nodes at depth n, and the function k
n
grows exponentially
with the depth n. See asymptotic analysis.
• common logarithm (6): The common logarithm of a quantity x is the logarithm
base 10 of x:log
10
x. See binary logarithm, natural logarithm.
• complete binary tree (7, 10): A complete binary tree is a binary tree of k levels
and 2
k
− 1 nodes. It is thus a binary tree in which every node in all levels
except the level of leaf nodes has exactly two children, and all the leaf nodes
are at the same level. See binary tree, incomplete binary tree.
• complete ternary tree (10): A complete ternary tree is a ternary tree of k levels
and
1
2
(3
k
− 1) nodes. It is thus a ternary tree in which every node in all levels
except the level of leaf nodes has exactly three children, and all the leaf nodes
are at the same level. See complete binary tree.
352 APPENDIX CGLOSSARY
• connected component (9, 13): A connected component in a graph is a subgraph
of the graph that is a connected graph and to which no further nodes and arcs
can be added from the original graph without creating a subgraph that is not
connected. See connected graph.
• connected graph (9, 13): A graph is said to be connected if a path (directed in
the case of a directed graph) exists between any two nodes in the graph.
• constant time (6): A computation is said to run in constant time if the asymp-
totic running time is a fixed constant and is independent of the size of the data
presented to the algorithm. See asymptotic analysis, exponential time, linear
time, logarithmic time, quadratic time.
• context (8): The context of an executing program includes the memory space
allocated to the program, the binary data of the program executable, and the
values currently assigned to the variables of the program. The notion of context
is that, in theory, the context of the program could be made independent of
the rest of the computer in which it is being executed and assigned hardware
resources like a CPU, and that all that is necessary for continuing the program
execution would be present.
• cycle (9, 13): A cycle in a graph consists of a set of nodes v
1
,...,v
n−1
,v
n
and a
set of arcs <v
1
,v
2
>, <v
2
,v
3
>,...,<v
n−1
,v
n
><v
n
,v
0
> that define a path from
v
1
to v
n
and then back to v
0
.
• data payload (2): The data payload of a structure is the actual data carried by
that structure, as opposed to other information (often referred to as metadata)
used for management of the structure. For example, each Internet packet has
metadata fields for source, destination, message ID, and packet ID, in addition
to the data payload. The data payload for an Internet packet is the actual
portion of the Internet message that is carried by that particular packet.
• decision tree (10): A decision tree is a tree representing a nested structure of
decisions to be made. For example, any program segment that is a group of
nested
if()
{
}
else if()
{
}
else
{
}
statements represents a decision tree.
C.2 Terms Used in This Book 353
• degree of a node (9, 13): See node degree.
• deprecated (4): In the world of computing, a feature or practice is considered
deprecated if it is possible under the rules of a programming language or
guidance sheet to use that feature or follow that practice, but it is considered
inadvisable to do so. Many methods in Java are deprecated because they have
been superseded by other methods. Although the deprecated methods will
continue to exist in order to support code already written, the opinion of those
responsible for Java is that the newer methods are sufficiently superior that
the old methods should simply not be used for new code.
• depth-first search, depth-first traversal (10): When a tree is visualized in
standard form, with the root node at the top and the tree descending from
the root, a depth-first traversal is accomplished by descending from the root
all the way to visit some leaf node, then backing up and descending to visit
another leaf node, and so forth. See breadth-first traversal, depth of a node,
height of a node, inorder traversal, postorder traversal, preorder traversal.
• depth of a node (10): The depth of a node inarootedtreeisthenumberof
arcs that must be traversed in order to move upward from the node to reach
the root. The root has depth 0. The children of the root have depth 1, and so
forth. See height of a node.
• deque (7): A deque is a double-ended queue, a linear list data structure in
which data can be added to or removed from the list at either end but only
at the two ends. See queue.
• directed graph (9, 13): A directed graph is a graph in which one or more of the
arcs is directed from an originating node to a terminating node and represents
a connection only in that direction. See undirected graph.
• discipline of programming (3): The term discipline of programming usually
uses the word “discipline” in the sense of monastic orders to refer to a set
of guidelines and practices that curb excessively independent behavior and
encourage standards that are felt to be the best practice.
• distributed memory parallel computer (11): In a distributed memory parallel
computer each of the parallel processors has direct access to read and/or write
to or from only a subset of the entire memory in the computer. Read/write
access to memory that is directly controlled by another processor must be
done by requesting such actions of the processor controlling the other memory.
This is the model of computation of a Beowulf cluster, which is essentially
a collection of standalone computers with an interconnection network and a
software library that facilitates the necessary memory requests. See shared
memory parallel computer.
• divide and conquer (3, 6): See recursion, recursive divide and conquer.
• document authentication (12): Document authentication is achieved in a
protocol for handling documents when a document that is transmitted can be
354 APPENDIX CGLOSSARY
verified to be authentic, that is, what it claims to be. See document integrity,
document nonrepudiation.
• document integrity (12): Document integrity is achieved in a protocol for
handling documents when a document that is received can be guaranteed to
be the document that was transmitted, with no alterations. See document
authentication, document nonrepudiation.
• document nonrepudiation (12): Document nonrepudiation is achieved in a
protocol for handling documents when a document received by an individual B
and allegedly sent by an individual A cannot be repudiated by A as not having
been sent by him or her. See document authentication, document integrity.
• doubly-linked list (4): A doubly-linked list is a linked list in which links between
nodes exist in both directions, forward to the next node and backward to the
previous node. See singly-linked list.
• dynamic data structure (3, 4): A data structure is dynamic when data can be
added to or removed from the structure while the structure is being processed.
The queue of executable processes in a computer is always dynamic because
it is always present and is changing with the user’s actions. Payroll data for
a company will usually not be dynamic because changes to the payroll data
will probably not be permitted during the execution of the payroll check
program.
• edge (9, 13): See graph.
• edge weight (13): An edge weight in a graph is a numerical value associated
with an edge that usually represents a cost or capacity. A graph that represents
cities on a map could have edge weights representing the distance between
cities. A graph that represents nodes in the Internet could have edge weights
representing bandwidth between the nodes.
• embarrassingly parallel (10): A computation is said to be embarrassingly
parallel if there is a trivial way in which to break up the computation into a
large number of completely independent subcomputations each of which can
be executed in parallel with the others.
• encapsulation of data (2): Data in a computer program is said to be
encapsulated when all privileges for access to that data are tightly controlled,
essentially on a need-to-know or need-to-use basis.
• Eulerian cycle (13): An Eulerian cycle in a graph is a cycle that visits every
edge exactly once. See Hamiltonian cycle.
• Eulerian path (13): An Eulerian path in a graph is a path that visits every
edge exactly once. See Hamiltonian path.
• exponential time (6): An algorithm or program runs in exponential time if
the asymptotic running time is O(k
N
)forsomek>1 when the algorithm or
program is run on data inputs of size N. See asymptotic analysis, constant
time, linear time, logarithmic time, quadratic time.
C.2 Terms Used in This Book 355
• Fibonacci sequence (8): The Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...
is the sequence of integers F(n) generated by the formula
F(n)=F(n −1) + F(n − 2)
subject to the initial conditions F(0) = 0 and F(1) = 1.
• field (1): See flat file.
• fixed-format records (1): Records are stored with a fixed format if each field
within a record is permitted a fixed number of bytes. For example, integer
data is almost always stored with 4 bytes for each integer. When a record is
stored with a fixed format, the size of each record is fixed as the sum of the
number of bytes necessary for each field plus the fixed number of bytes used
by the data structure for managing the individual record.
• flat file (1, 3): Data is arranged in a flat file if it is arranged in a fashion
similar to a spreadsheet, with some variable number of rows, each of which is
referred to as a record, and some fixed number of columns, each of which is
referred to as a field.
• forest of trees (9): A graph is a forest of trees if as a graph it comprises one
or more connected components each of which is a tree.
• free list (4): In many data structures, usually in legacy code, the structure
is implemented with memory space preallocated for the structure. In such
instances, the free list is the memory that has been allocated for the structure
but has not been used (yet) for storing data. The need for a free list has been
largely obviated by more modern programming languages and environments
that do automatic allocation and release of memory from a memory store,
which means the programmer does not need to manage memory in such an
explicit way.
• generics (1, 3, 5): The use of a Java generic permits programs to be written
that will operate on instances of any data type whatsoever. A “swap” method,
for example, does not need to have any information about the actual data
type of the two instances to be swapped; it needs only to be able to create
a temporary instance of that data type to be used for storing a value that is
overwritten during the swap process.
• graph (9, 13): A graph is a mathematical construct G = {V, E} comprising
a set of vertices V (sometimes called nodes) and a set of edges E (sometimes
called arcs), with an edge e = {v
1
,v
2
} between vertex v
1
and vertex v
2
representing a connection.
• greatest common divisor (10): The greatest common divisor of two integers m
and n is the largest integer g that divides both m and n leaving no remainder.
• greedy algorithm (9): An algorithm is said to be a greedy algorithm if, at any
stage of the computation, when a choice is to be made, the algorithm takes
356 APPENDIX CGLOSSARY
the greedy, intuitively obvious, hopeful choice of whatever looks to be best at
the time.
• Hamiltonian cycle (13): A Hamiltonian cycle in an undirected graph is a cycle
that visits each vertex exactly once, except for the vertex at which the cycle
begins and ends and which is thus visited twice. See Eulerian cycle.
• Hamiltonian path (13): A Hamiltonian path in an undirected graph is a path
that visits each vertex exactly once. See Eulerian path.
• hash collision (12): A hash collision occurs when two different data sources are
mapped by a hash function to the same storage location. See hash function,
hash table.
• hash function (12): A hash function is a function that creates, from some part
of the data of a data item, a storage subscript location into which to store the
data item. See hash table.
• hash table (12): A hash table is an array in memory of storage locations into
which data is mapped by a hash function. See hash function.
• hash table load factor (12): The load factor for a hash table is the fraction
of the preallocated storage locations that are expected to be used for actual
storage of data. If a hash table is preallocated for 2
20
entries, and is used
for storing 2
17
data entries, then it has a load factor of 1/2
3
=1/8. See hash
function, hash table.
• heap (7, 10): A heap is a data structure that satisfies the heap property. See
heap property.
• heap property (10): An array A[.] is said to satisfy the (minimum) heap
property if for any three locations A[i], A[2*i], A[2*i+1] in the array, the
key value associated with the data at location i is smaller than the key values
for the data at locations 2*i and 2*i+1. The maximum heap property is
defined analogously.
• heapsort (1): Heapsort is a sorting algorithm with an O(N lg N) average-case
and O(N lg N) worst-case running time that can be run as an in-place
algorithm and is characterized by recursively creating a heap from the data,
removing the smallest element from the top of the heap, and then rebuilding
the heap. See asymptotic notation, bubblesort, in-place algorithm, insertionsort,
mergesort, out-of-place algorithm, quicksort.
• height-balanced (10): A tree is said to be height-balanced if no leaf node is
“much farther” from the root than is any other leaf node. This is not a precise
definition.
• height of a binary tree (10): The height of a rooted binary tree is the largest
number of arcs that must be traversed in order to move downward from the
root node to a leaf node.
• height of a node (10): The height of a node inarootedtreeisthelargest
number of arcs that must be traversed in order to move downward from the
node to a leaf node. See depth of a node.
C.2 Terms Used in This Book 357
• heuristic (1, 8): A heuristic is a computational strategy that is not guaranteed
to be successful but which, under many circumstances, will work.
• incident, incident node (9, 13): An edge in a graph is incident on a node if the
node is one of the two nodes that form the edge.
• incomplete binary tree (7): A binary tree is incomplete if there are nodes other
than leaf nodes at the lowest level that have fewer than two children. See
complete binary tree.
• incremental update (1): An incremental update of a data structure takes
place when a small amount of data is added to the existing structure and
the organization that characterizes the data structure can be rebuilt without
a complete recomputation. Adding one element through insertionsort to a
sorted list, for example, is an incremental update.
• indegree of a node (9, 13): See node indegree.
• index (3, 12): An index is a list of retrieval keys for a data structure, with the
list in sorted order, and pointers to where the corresponding data elements
are located in the data structure.
• inorder traversal (10): When a binary tree is visualized in standard form, with
the root node at the top and the tree descending from the root, an inorder
traversal is accomplished by recursively visiting first the left child of a node,
then the node itself, then the right child. See breadth-first traversal, depth-first
traversal, depth of a node, height of a node, postorder traversal, preorder
traversal.
• in-place algorithm (11): An algorithm is said to execute in place if it requires
only a fixed amount of storage in addition to the storage necessary to store
the actual data on which the algorithm executes. See out-of-place algorithm.
• insertionsort (4, 11): An insertionsort is an in-place sorting algorithm in
which N items are sorted by running N loops; each loop assumes that it is
operating on a sorted list of k<N elements and increases the length of the
sorted list by 1 by inserting a new element into its proper place in the list.
See asymptotic notation, bubblesort, heapsort, in-place algorithm, mergesort,
out-of-place algorithm, quicksort.
• interior node (10): A node in a tree is an interior node if it is not a leaf node.
See leaf node.
• Internet packets (1): One of the reasons that the Internet works is that an
individual message or data file to be sent across the net is broken up into a set
of packets, each of which contains a great deal of header information regarding
source, destination, packet sequence number in the entire message, and a
fixed-size block that is a subset of the entire data of the message. In this way
packets can be made to have a fixed size and can be sent independently from
source to destination, arriving perhaps out of order and perhaps traveling along
different paths. It is the job of the router at the destination to put the packets
back together so the data is reorganized into the original message or file.
358 APPENDIX CGLOSSARY
• JCF (5, 12): The Java Collections Framework is a set of classes built into
the Java package that supports program development by providing routine
structures like stacks, queues, priority queues, hash tables, and similar
containers for data.
• key (11): The key for a data item to be stored, retrieved, or searched for is the
information element that is used to identify the data item. Search keys are
often names, Social Security numbers, telephone numbers, or driver’s license
numbers, but can also be other information elements created by the software
from the data so as to provide unique identifiers.
• leaf node (10): A leaf node in a tree is a node with no children. See interior node.
• left child (10): In a binary tree, the left child of a given node is the child that
descends to the left when the tree is presented in standard form. See right child.
• level of a tree (10): The nodes at level k of a tree comprise all nodes in the
tree whose depth is k.
• level traversal (10): See breadth-first traversal.
• linear search (6): A linear search is performed on an array of data when the
array is processed one item at a time, from beginning to end, comparing the
data in the array against the key that is being searched for.
• linear time (6): An algorithm or program runs in linear time if the asymptotic
running time is O(N) when the algorithm or program is run on data inputs of
size N. See asymptotic analysis, constant time, exponential time, logarithmic
time, quadratic time.
• linked list (4): A linked list is a data structure characterized by having
independent nodes carrying data, a distinguished head node that is the first
node in the linked list, and a pointer from any given node (including the head)
to the next node in the list.
• little oh (6): See asymptotic notation.
• load balancing (10): Load balancing refers to the goal of dividing up the work
to be done by several processors or processes into roughly equal sizes so that
all processors will contribute to the common computation and take about the
same length of time to complete their share of the task at hand.
• logarithm, binary (6): See binary logarithm.
• logarithm, common (6): See common logarithm.
• logarithm, natural (6): See natural logarithm.
• logarithmic time (6): An algorithm or program runs in logarithmic time if
the asymptotic running time is O(lg N) when the algorithm or program is run
on data inputs of size N
. See asymptotic analysis, constant time, exponential
time, linear time, quadratic time.
• main term (6): The main term in an expression for the asymptotic work required
for an algorithm is the function term that determines the big Oh asymptotic
C.2 Terms Used in This Book 359
running time of the algorithm. A polynomial f(x)=a
n
x
n
+ ···+ a
1
x + a
0
,
for example, has x
n
as its main term.
• max-heap (7, 10): See heap property.
• maximal clique (13): A clique in a graph is a maximal clique if no nodes can
be added to the subgraph that is the clique without creating a subgraph that
is no longer a clique. See clique.
• mergesort (1, 11): Mergesort is a sorting algorithm with an O(N lg N) average-
case and worst-case running time that must be run as an out-of-place algo-
rithm, and is characterized by a recursive merge of pairs of sorted lists of size
k to form single lists of size 2k. See asymptotic notation, bubblesort, heapsort,
in-place algorithm, insertionsort, out-of-place algorithm, quicksort.
• min-heap (7, 10): See heap property.
• misfeature (4): A computer program is (humorously) said to have a misfeature
if there is some aspect of the program that decreases its normal ease of use.
It is a feature of some email programs that attachments after the first for a
given email message have as a default storage location the directory in which
the first attachment was stored; it would be something of a misfeature if the
mailer reset to a default location because one can imagine most instances
of multiple attachments being sufficiently related to one another that saving
them in the same directory would happen more often than not.
• multigraph (9, 13): A multigraph is a graph in which two nodes are permitted
to be connected by more than one edge.
• natural logarithm (6): The natural logarithm of a quantity x is the logarithm
base e of x:log
e
x. This is often written ln x. See binary logarithm, common
logarithm.
• node (4, 7, 9, 13): See graph.
• node degree (9, 13): The degree of a node in a graph is the number of edges
incident on the node. See node indegree, node outdegree.
• node indegree (9, 13): The indegree of a node in a graph is the number of
edges entering the node. In an undirected graph this is the same as the degree
and the outdegree; in a directed graph this is the number of edges directed
into the node. See node degree, node outdegree.
• node outdegree (9, 13): The outdegree of a node in a graph is the number of
edges leaving the node. In an undirected graph this is the same as the degree
and the indegree; in a directed graph this is the number of edges directed out
from the node. See node degree, node indegree.
• NP-complete problem (13): The class P contains all the problems for which
we have found polynomial-time algorithms for their solution. The class NP
contains the problems for which we can check a putative solution in polynomial
time. A problem is said to be NP-complete if it is in the class NP and if any
360 APPENDIX CGLOSSARY
other problem in the class NP can be reduced to it in polynomial time. The
Boolean satisfiability and the Hamiltonian cycle problem are both in NP.
They are also NP-complete problems because there is a way to transform, in
a polynomial number of operations, an instance of SAT into an instance of
the Hamiltonian cycle problem, and conversely.
• objective function (1, 8, 10): An objective function is a function to be maximized
or minimized during a computation as a measure of success of the computation.
• one-time work (6): Most computer programs are useful because they perform
some repetitive computation in a loop. The one-time work associated with an
algorithm or computation is the work done before the loop begins, perhaps to
set up the execution of the loop, or after the loop ends, perhaps to aggregate
results from the loop. It is work done once for the entire computation, as
opposed to once for every iteration of the loop.
• outdegree of a node (9, 13): See node outdegree.
• out-of-place algorithm (11): An algorithm is said to execute out of place if
it requires, in addition to the storage necessary to store the actual data on
which the algorithm executes, additional storage space that is proportional to
the storage space for the actual data. See in-place algorithm.
• palindrome (4): A palindrome is a sequence of characters, such as “radar,”
that reads the same forward and backward.
• parent node (10): When a tree is visualized in standard form, with the root
node at the top and the tree descending from the root, the parent of a given
node is the node connected to the given node by an upward arc. See child node.
• parse (2): To parse a sequence of text characters is to break the sequence into
syntactic tokens based on separator characters (like blank spaces, tabs, and
newline characters) and to obtain a semantic understanding of the text by
applying the rules of the underlying language.
• path (9, 13): A path in a graph is a sequence of edges that connect tail to head
e
0
= <v
i
0
,v
i
1
>,
e
1
= <v
i
1
,v
i
2
>,
e
2
= <v
i
2
,v
i
3
>,
...,
e
n−1
= <v
i
n−1
,v
i
n
>.
from an origin vertex v
i
0
to a destination vertex v
i
n
.
• pathological cases (1): A pathological case of data for an algorithm is an example
of data on which the algorithm would perform most poorly. Pathological cases,
even if they are highly unusual, must nonetheless be considered as possible
when choosing or analyzing an algorithm for a particular computational task.
C.2 Terms Used in This Book 361
• portable code (3): Code (programs) are said to be portable if they can be moved
from one computer to another and still execute correctly. Java, for example, is
supposed to be “write once, run everywhere” under the premise that Java is so
completely standardized that a correct Java program can run on any machine
with a standard Java environment. Realizing that no serious program can really
be completely portable, the term is usually qualified to indicate the range of
supported machines, operating systems, compilers, and run-time environments.
• postorder traversal (10): When a binary tree is visualized in standard form,
with the root node at the top and the tree descending from the root, a
postorder traversal is accomplished by recursively visiting first the left child
of a node, then the right child, and then the node itself. See breadth-first
traversal, depth-first traversal, depth of a node, height of a node, inorder
traversal, preorder traversal.
• preorder traversal (10): When a binary tree is visualized in standard form,
with the root node at the top and the tree descending from the root, a
preorder traversal is accomplished by recursively visiting first the node itself,
then the left child of the node, and then the right child. See breadth-first
traversal, depth-first traversal, depth of a node, height of a node, inorder
traversal, postorder traversal.
• primary key (1, 9): The primary key used to store data is the key that is assumed
to be the key used for the “usual” access to the data. It will usually be the case
that the physical storage structure of the data is determined by the structure
that would make access by the primary key most efficient because access by the
primary key would be assumed to occur more often than access by any other key.
• priority queue (7): A priority queue is a data structure in which the “next
item to be processed” is at an identifiable “first” location in the structure, and
this property is reestablished after the first item is removed for processing, so
that the “next” item is present in steady state at the “first” location.
• probe (3, 12): The search through a set of data for an individual item usually
requires a process of locating a particular item, comparing that item’s key
against the sought-for key to determine if they match, and then repeating
the location and comparison until the match is found. Each such location and
comparison is called a probe, and search algorithms are evaluated based on
the expected number of probes required before the sought-for item is found.
• prudent programmer (5): The standard navigational charts used in the United
States all carry the warning: “The prudent mariner will not rely solely on any
single aid to navigation, particularly on floating aids.” This carries the force of
law, in that a mariner who causes an accident by acting imprudently can be held
liable for the accident. By analogy, the prudent programmer will not rely upon
best-case conditions to hold true but will instead anticipate possible problems
and write code that will be robust under the most hostile of circumstances.
362 APPENDIX CGLOSSARY
• pseudocode (3): A pseudocode description of an algorithm or process is a
description that has most of the precision and stepwise sequencing of a
computer program, but is written in a form more closely resembling English
and without paying attention to the strict syntactic requirements of a
programming language.
• pseudorandom number (12): A sequence of numbers is said to be pseudoran-
dom if it is produced by a deterministic process but possesses the statistical
characteristics that a sequence of truly random numbers would possess.
• push-down stack (7): A push-down stack, or more simply just a stack, is a list
data structure in which all additions to and removals from the structure are
made at one end of the list, called the top of the stack.
• quadratic time (6): An algorithm or program runs in quadratic time if the
asymptotic running time is O(N
2
) when the algorithm or program is run on
data inputs of size N. See asymptotic analysis, constant time, exponential
time, linear time, logarithmic time.
• queue (7): A queue is a list data structure in which all additions to the
structure are made at a specific location called the tail and all removals from
the structure are made at a specific location called the head. See deque.
• quicksort (1, 11): Quicksort is a sorting algorithm with an O(N
2
) worst-case
but O(N lg N) average-case running time that can be run as an in-place
algorithm and is characterized by a recursive splitting of the yet-to-be-sorted
data into keys smaller than and keys larger than a chosen pivot element. See
asymptotic notation, bubblesort, heapsort, in-place algorithm, insertionsort,
mergesort, out-of-place algorithm.
• random access (4): A program has random access to its data if a particular
data item can be retrieved without processing through all the data stored
prior to that item. An array or ArrayList, for example, permits random
access by subscript value; a linked list does not permit random access because
a data item can only be reached by traversing the list.
• record (1): See flat file.
• recursion (8): A technique for solving a problem uses recursion if the problem
is solved by using the same technique on successively smaller versions of the
same problem.
• recursive divide and conquer (3, 6): A recursive divide-and-conquer algorithm
is an algorithm that progresses from one stage of the computation to another
by cutting the problem into smaller pieces and then calling itself on each
of the smaller problem pieces. In many instances, the algorithm tries to cut
the problem in half at each stage and call itself on each of the two nearly
equal-sized subproblems. See recursion.
• recursive program, recursion (8): A recursive program is a program that calls
itself.
C.2 Terms Used in This Book 363
• relation (9): A relation R on a set S is a set of ordered pairs R = {<s
1
,s
2
>}
in which s
1
,s
2
∈ S. The relation “less than” on the set S = {1, 2, 3, 4} is the
set of ordered pairs
R = {<1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>, <3, 4>}.
This is the formal statement of what we would normally recognize as
1 < 2, 1 < 3, 1 < 4,
2 < 3, 2 < 4,
3 < 4.
• religious issues (2): An issue is considered (humorously) a religious issue if
there is genuine disagreement as to how that issue ought to be decided or
if the issue should properly be viewed as a matter of personal taste. The
choice between Emacs and vi as an editor, for example, or the choice between
Firefox
R
and Chrome
TM
for a browser, is a religious issue. See the Jargon File.
• reverse Polish notation (7): Reverse Polish notation (RPN) is the notation for
arithmetic expressions that was developed by the Polish mathematician Jan
Lukasiewicz. It does not use parentheses or other mechanisms, relying instead
on the convention that an operator (+, −, ∗,or/)istobeappliedtothe
two most-recently referenced numerical quantities. RPN was the standard for
many years for Hewlett-Packard hand calculators and is a standard example
used in discussing stack-based computation.
• right child (10): In a binary tree, the right child of a given node is the child that
descends to the right when the tree is presented in standard form. See left child.
• root of a tree (1, 7, 10): The root of a tree is a node in a tree that has been
identified as the root. When the tree is presented in standard form, the root
is at the top of the display and other nodes descend from the root.
• semantics (3): Semantics refers to the meaning of an expression in a language. A
program can be syntactically correct, that is, be a legal program in a language,
while not being semantically correct, if the effect of the program is to compute
something other than what is intended. For example, the program fragment
sum=0;
for(int = 1; i < 10; ++i)
{
sum += i;
}
is syntactically correct as a program fragment in Java. If the semantics of that
fragment were to sum the first 10 integers, however, then the program would
364 APPENDIX CGLOSSARY
be semantically incorrect because what it does instead is to compute the sum
of the first 9 integers. See syntax.
• shared memory parallel computer (11): In a shared memory parallel computer,
each of the parallel processors has complete access to read and/or write to or
from all the memory in the computer. The memory is shared among all proces-
sors, and no restrictions are placed on any processor’s use of any memory due to
the presence of the other processors. See distributed memory parallel computer.
• shortest path (13): The shortest path between two nodes in a graph is a
path with the fewest number of arcs. This may not be unique; there may be
different shortest paths of equal length.
• simple path (13): A path in a graph is a simple path if each of the nodes in
the path is distinct.
• singly-linked list (4): A singly-linked list is a linked list in which links between
nodes exist only in the forward direction, from the current node forward to
the next node. See doubly-linked list.
• spaghetti code (2): A program is referred to as spaghetti code if the logical flow
of control in the program is tangled like spaghetti on a dinner plate. Programs
are more likely to be correct from the beginning and maintainable in the future
if their flow of control is clean. Programs with a complicated set of controls will
be hard to get right and hard for someone new to the program to understand.
• spanning tree (10, 13): A spanning tree in a connected graph is a subgraph
that is a tree and that contains all the nodes of the graph.
• sparse graph (13): A sparse graph is a graph in which there are very few edges
compared to the number of nodes. This imprecise term is used very much like
the imprecise term sparse matrix.
• sparse matrix (13): A matrix of N rows and M columns is a sparse matrix if the
number of nonzero entries is very small compared to the total number N · M
of possible entries. This is not a precise term. Standard matrix algorithms deal
with a matrix stored as a two-dimensional array of numbers, processing matrix
operations as loops across rows and columns. If the matrix is sparse, it can
be more efficient to store only the nonzero entries in something like a linked
list and run loops that need only look at the nonzero entries. Because there
are separate algorithms and storage structures for dealing with matrices like
this, a matrix is usually considered (imprecisely and recursively) to be sparse
if the number of nonzeros is small enough that a sparse matrix algorithm is
more efficient than a standard matrix algorithm.
• stable sort (11): A sort is considered stable if the following property holds. For
any pairs A and B in the list to be sorted, if A = B and A appears before B in
the original list, then A will continue to appear before B in the newly sorted
list. That is, a stable sort does not change the prior ordering of elements
with equal keys. Implemented correctly, bubblesort, insertionsort, mergesort,
C.2 Terms Used in This Book 365
and quicksort are stable sorts, while heapsort is not. The stability of a sort is
relevant to the problem of sorting on multiple keys.
• stack (7): See push-down stack.
• state of execution (1): A process is in a state of execution if it has begun to
execute and has not yet finished executing. A process that has been suspended,
either because it needs more of some resource on which to work (such as
more data) or because of the usual multiprocessing in any modern operating
system, is still in a state of execution, even if it is not actually being executed
by the CPU.
• Stirling’s formula (6): Stirling’s formula is one of the standard approximations
for the factorial of an integer. Specifically, the approximation is
N!=
√
2πN
N
e
N
e
α
N
,
where
1
12N +1
<α
N
<
1
12N
.
• subgraph (9, 10, 13): A subgraph of a graph G =(V, E) is another graph
G
=(V
,E
) for which V
⊂ V and E
⊂ E and the edges in E
only connect
nodes in V
. That is, a subgraph is exactly what one would think it is: a subset of
the nodes, together with some subset of the edges that join nodes in the subset.
• syntax (3): The syntax of a programming language consists of the rules by
which one may construct legally correct statements in that programming
language. See semantics.
• Syracuse problem (8): See 3n +1problem.
• token (2): In programming languages and compiling, a token is a unit of
input consisting of the sequence of input characters in between two instances
of white space. To the Java compiler, for example, white space includes
blank spaces, tabs, and newline and carriage return characters. Parentheses,
open and close brackets and braces, and semicolons would also start or end
processing for tokens and would be considered to be separate tokens.
• total order (7): A total order on a set of objects is a mathematical relation
(which we can refer to as “less than or equal to”) such that for any two
elements x and y in the set, either “x is less than or equal to y”istrueor“y
is less than or equal to x” is true.
• transaction processing (1): A computation can be said to be transaction
processing if the primary computation is the processing of a stream of
individual transactions each of which is largely unrelated. The canonical
example of transaction processing would be the handling of individual retail
366 APPENDIX CGLOSSARY
receipts by a large store. Each receipt affects inventory, billing, credit card
charges, and so forth but is essentially independent of any other receipt.
• transitive closure (9): The transitive closure of a mathematical relation is
a subset of the relation such that every element of the transitive closure is
related to every other element of the transitive closure, and no element of
the set on which the relation is defined can be added to the closure without
violating this property of all elements being related. The connected component
in a graph is the transitive closure of any node in the component under the
relation of “connected by an arc.” See connected component.
• transitive relation (9): A mathematical relation R on a set S is transitive if
for any three elements a, b,andc in S,ifaRb and bRc are true, then aRc is
true. The canonical transitive relations are equality, <, ≤, >,and≥. If, for
example, we have x ≤ y and y ≤ z, then we know that x ≤ z because the ≤
relation is transitive.
• tree (7, 9, 10): The following two definitions can be shown to be equivalent.
1. A tree is a connected graph with n nodes and n − 1 edges.
2. A tree is a connected graph with no cycles.
• tree search (1): Searching through a tree usually refers to a process of traversing
a tree whose nodes represent decisions in a process or the status of a game or
computation. Chess-playing programs, for example, expand the tree of moves
and countermoves from the current position and search among the nodes for
the board position most advantageous to the current player. See tree traversal.
• tree traversal (10): Traversing a tree refers to the following of the paths and
the examining of the nodes of the tree in some specified order. See breadth-first
traversal, depth-first traversal, inorder traversal, postorder traversal, preorder
traversal.
• UML diagram (2): Unified Modeling Language (UML) is one of the ways
(and becoming the standard way) in which the structure and interactions
among various pieces of a software system are described. A UML diagram is a
graphical display of the variables, methods, parameters, returned values, and
public or private accessibility of an object or class in a software package. From
the UML diagram one can see among other things which classes are responsible
for which parts of the computation and whether the data on which the methods
operate is to be passed in as parameters or resides locally within the class.
• undirected graph (9, 13): An undirected graph is a graph in which none of the
arcs is directed. See directed graph.
• unrooted tree (10): An unrooted tree is a tree with no node identified as the
root of the tree. See root of a tree.
• unweighted graph (9): An unweighted graph is a graph in which none of the
edges has an edge weight associated with it. See edge weight.
• vertex (9, 13): See graph.
C.2 Terms Used in This Book 367
• weighted graph (9): A weighted graph is a graph in which one or more of the
edges has an edge weight associated with it. See edge weight.
• worst-case behavior (1, 6, 11): The worst-case behavior of an algorithm is
the behavior that leads to the worst-case running time. For example, the
worst-case behavior of insertionsort into increasing order is exhibited when
an item is added to an array of length N and the new item’s key is smaller
than all other keys for items already in the array. In this case, the new item’s
key must be compared with all other keys for items in the array and the
new item pulled forward to the leading position in the array. This requires N
comparisons and is the worst-case situation for insertionsort. See average-case
behavior, best-case behavior.
• worst-case running time (1, 6, 11): The worst-case running time of an algorithm
is the running time of the algorithm under the worst-case conditions. See
average-case running time, best-case running time.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.