Glossary
A form of abstraction that arises from the use of
defined types. An ADT consists of a class of objects, a defined
set of properties of those objects, and a set of operations for
processing the objects.
abstraction
The description of data structures at a conceptual
level, apart from their implementation using a particular technique
and language.
abstract syntax treeSee
parse tree.
access adjustment
A method of changing the access mode of an inherited
member from within a derived class. For example, a derived class
may inherit all members from a base class in protected mode, and
then make some members public by means of access adjustments.
See also access mode,
base class, derived class,
and inheritance.
A symbol (public, protected, or private)
that specifies the kind of access that clients have to a server's
data members and member functions. See also private member,
protected member, and
public member.
accumulator
A variable used for the purpose of summing successive
values of some other variable.
actual parameter
A variable or expression contained in a function
call and passed to that function. See also formal parameter.
Often called address of a memory location, this is
an integer value that the computer can use to reference a location.
See also value.
ADTSee abstract data type.
ADT generality rule
An abstract data type should not be limited by the
types of its components. Wherever possible, users should be able
to specify the component types of a generic abstract data type.
ADT implementation rule
An implementation of an ADT must provide an interface
that is entirely consistent with the operations specified in the
ADT's definition.
ADT layering rule
Existing abstract data types should be used to implement
new abstract data types, unless direct control over the underlying
data structures and operations of the programming language is
a critical factor. A well-designed implementation consists of
layers of ADTs.
ADT use rule
An algorithm that uses an ADT should access variables
of that abstract data type only through the operations provided
in the ADT definition.
algorithm
A finite sequence of effective statements that, when
applied to the problem, will solve it.
alias
A situation in which two or more identifiers in a
program come to refer to the same memory location. An alias can
become the cause of subtle side effects.
analysis phase
The first phase of the software system life
cycle in which the systems analyst determines the user's needs
and develops formal specifications describing the proposed system
and its requirements.
ancestor
A tree node that is hierarchically related to another
tree node at a lower level in the tree.
application software
Programs designed for a specific use.
A value or expression passed in a function call.
arithmetic/logic unit (ALU)
The part of the central processing unit (CPU) that
performs arithmetic operations and evaluates expressions.
array
A data structure whose elements are accessed by means
of index positions.
The relative position of the components of an array.
artificial intelligence (AI)
The field of computer science in which the goal is
to program the computer to mimic intelligent human behavior.
The American Standard Code for Information Interchange
ordering for a character set.
A computer language that allows words and symbols
to be used in an unsophisticated manner to accomplish simple tasks.
assertion
Special comments used with selection and repetition
that state what you expect to happen and when certain conditions
will hold.
assignment statement
A method of putting values into memory locations.
A data structure whose two parts are a key and a
value.
association list
A data structure consisting of a set of associations.
See also association.
attribute
A property that a computational object models, such
as the balance in a bank account.
automatic program synthesis
A process whereby one computer program can be given
the specifications for another computer program, generate the
code to satisfy those specifications, and then prove the correctness
of that code.
Backus-Naur grammar
A standard form for defining the formal syntax of
a language.
The class from which a derived class inherits attributes
and behavior. See also derived class
and inheritance.
behavior
The set of actions that a class of objects supports.
The arrangement of data items prior to the start
of a sort function to finish in the least amount of time for that
particular set of items. See also worst case.
big-0 analysis
A technique for estimating the time and space requirements
of an algorithm in terms of order of magnitude.
big-0 notation
Saying that an algorithm is 0(f(n)) indicates that
the function f(n) may be useful in characterizing how efficiently
the algorithm performs for large n. For such n, we are assured
that the operations required by the algorithm will be bounded
by the product of a constant and f(n).
bin sort See radix sort.
A digit, either 0 or 1, in the binary number system.
Program instructions are stored in memory using a sequence of
binary digits. Binary digits are called bits.
binary search
The process of examining a middle value of a sorted
array to see which half contains the value in question and halving
until the value is located.
binary search tree
A binary tree with the ordering property.
binary tree
A tree such that each node can point to at most two
children.
binary tree search
A search algorithm driven by the hierarchical relationships
of data items in a tree with the ordering property.
binding time
The time at which a program variable is bound to
a particular value. This can occur either at compile time or at
run time.
bit See binary digit.
The method of testing a module whereby the tester
Is aware of only what the module is supposed to do, not the method
of implementation or the internal logic. See also white box testing.
The area of program text within a compound statement,
containing statements and optional data declarations.
blocked queue
In an operating system, the queue of processes that
have requested a resource currently owned by another process.
An expression whose value is either true or false.
See also compound Boolean expression
and simple Boolean expression.
bottom-up testing
Independent testing of modules.
boundary conditions
Values that separate two logical possibilities. These
are important cases to check when testing a module.
boundary folding
A variation on shift folding: in boundary folding,
the digits of every other numeric section are reversed before
the addition is performed.
branch
In a tree, a link between a parent and its child
node.
breadth-first traversal
A visiting of all nodes in a graph; it proceeds from
each node by first visiting all nodes adjacent to that node.
B-tree
An efficient, flexible index structure often used
in database management systems.
Rearranges elements of an array until they are in
either ascending or descending order. Consecutive elements are
compared to move (bubble) the elements to the top or bottom accordingly
on each pass. See a heap sort,
insertion sort, merge sort,
quick sort, radix sort,
selection sort, and shell sort.
bucket
In bucket hashing, a contiguous region of storage
locations.
bucket hashing
Method of handling collisions whereby the hashing
function sends the key to a bucket If locations rather than a
single location. The key is then placed by performing a sequential
search within the bucket.
bus
A group of wires imprinted on a circuit board to
facilitate communication between components of a computer.
byte
A sequence of bits used to encode a character in
memory. See also word.
Any reference to a subprogram by an executable statement.
Also referred to as invoke.
central processing unit (CPU)
A major hardware component that consists of the arithmetic/logic
unit (ALU) and the control unit.
character set
The list of characters available for data and program
statements. See also collating sequence.
child node
A node that descends from another node in a tree.
children
Nodes pointed to by a node in a tree.
circular linked list
A linked list whose last node points to the
first or head node in the list.
class
A description of the attributes and behavior of a
set of computational objects.
class constructor
A member function used to create and initialize
an instance of a class.
class declaration module
An area of a program used to declare the data members
and member functions of a class.
class destructor
A member function defined by the programmer and automatically
used by the computer to return dynamic memory used by an object
to the heap when the program exits the scope of the object. See
also dynamic memory.
class implementation module
An area of a program used to implement the member
functions of a class.
class template
A special kind of class definition that allows clients
to specify the component types of objects of that class.
client
A computational object that receives a service
from another computational object.
clustering
Occurs when a hashing function is biased toward
the placement of keys in a given region of the storage
space.
code (writing)
The process of writing executable statements that
are part of a program to solve a problem.
cohesive subprogram
A subprogram designed to accomplish a single task.
The particular order sequence for a character set
used by a machine. See also ASCII collating sequence
and EBCDIC collating sequence.
collision
Condition in which more than one key hashes to the
same position with a given hashing function.
A means of traversing a two-dimensional array whereby
all of the data in one column are accessed before the data in
the next column. See also row-major order.
comment
A nonexecutable statement used to make a program
more readable.
compatible type
Expressions that have the same base type. A parameter
and its argument must be of compatible type, and the operands
of an assignment statement must be of compatible type.
An error detected when the program is being compiled.
See also design error,
logic error, run-time error,
and syntax error.
compiler
A computer program that automatically converts instructions
in a high-level language to machine language.
Refers to the complete expression when logical connectives
and negation are used to generate Boolean values. See also
Boolean expression
and simple Boolean expression.
compound statement
Uses the symbols f-and I to make several simple statements
into a single compound statement.
conditional statement
See selection statement.
constant
A symbol whose value cannot be changed in the body
of the program.
constant definition section
The section where program constants are defined for
subsequent use.
constant parameter
A method of declaring a formal array parameter so
that the value of an actual array parameter will not change in
a function.
constant reference
A method of declaring a formal parameter so that
the actual parameter is passed by reference but will not change
in a function.
control structure
A structure that controls the flow of execution of
program statements.
control unit
The part of the central processing unit that controls
the operation of the rest of the computer.
copy constructor
A member function defined by the programmer and automatically
used by the computer to copy the values of objects when they are
passed by value to functions.
counter
A variable used to count the number of times some
process is completed.
coupling
The amount of interaction between a pair of modules.
cubic algorithm
A polynomial algorithm in which the highest nonzero
term is n3.
data
The particular characters that are used to represent
information in a form suitable for storage, processing, and communication.
data abstraction
The separation between the conceptual definition
of a data structure and its eventual implementation.
data flow diagram
A graphic tool used by systems analysts to represent
data flow and transformations as a conceptual process. Also referred
to as a bubble diagram.
data member
A data object declared within a class declaration
module.
A formal description of the set of values that a
variable can have.
data validation
The process of examining data prior to its use in
a program.
An infinite wait state in which two processes each
own system resources the other needs and will not release until
they have obtained the remaining resources they need. Also referred
to as fatal embrace.
debugging
The process of eliminating errors or "bugs"
from a program.
declaration sections
The sections used to declare (name) symbolic constants,
data types, variables, and subprograms that are necessary to the
program.
decrement
To decrease the value of a variable.
density
The number of storage locations used divided by the
total number of storage locations available.
density-dependent search technique
A Search technique whose efficiency is determined
solely by the density of the data.
depth-first traversal
A visiting of all nodes in a graph, proceeding from
each node by probing as deeply as possible along one path leading
from that node.
dereference
The operation by which a program uses a pointer to
access the contents of dynamic memory. See also dynamic memory
and pointer variable.
A class that inherits attributes and behavior from
other classes. See also base class
and inheritance.
An error such that a program runs, but unexpected
results are produced. Also referred to as a logic error. See
also compilation error,
run-time error, and syntax error.
design phase
The second phase of the software system life cycle.
In this phase, a relatively detailed design plan is created from
the formal specifications of the system produced in the analysis
phase.
dictionary
A data structure consisting of a set of associations.
See also association.
digit/character extraction
In creating a hashing function, the process of removing
from a key those digits of characters that may bias the results
of the function.
A graph having some edges that point in only one
direction.
diminishing increment sort
A sort in which the number of segments in any one
pass decreases with each successive pass. See also shell sort.
directional graph
See digraph.
divide-and-conquer algorithms
A class of algorithms that solves problems by repeatedly
dividing them into simpler problems. See also recursion.
division-remainder technique
A hashing technique that ensures that the result
will be a valid output. It uses the modulus operation to scale
the value into the proper range.
dominant term
The highest power of n in a polynomial. For large
n, the behavior of the entire polynomial will approach the behavior
of a polynomial that contains only that term.
doubly linked list
A linked list in which each node has two pointers
instead of one. One of these points to the previous node in the
list and the other points to the next node in the list.
A post-test loop examining a Boolean expression after
causing a statement to be executed. See also for loop,
loops, and while loop.
Memory allocated under program control from the heap
and accessed by means of pointers. See also heap
and pointer variable.
dynamic structure
A data structure that may expand or contract during
execution of a program. See also dynamic memory.
The Extended Binary Coded Decimal Interchange Code
ordering for a character set.
echo checking
A debugging technique in which values of variables and input data are displayed during program
execution.
edge
A direct connection between two nodes in a graph.
effective statement
A clear, unambiguous instruction that can be carried
out.
A semicolon used to indicate that no action is to
be taken. Also referred to as a null statement.
encapsulation
The process of hiding implementation details of a
data structure.
end-of-file marker
A special marker inserted by the machine to indicate
the end of the data file.
end-of-line character
A special character ('\O') used to indicate the end of a line of characters in a string or a file
stream.
entrance-controlled loop
See pretest loop.
enumerated data type
A set of symbolic constants defined by the programmer.
equivalence classes
A partitioning of all the logical possibilities that
can be checked when testing a module. All test cases within a
single equivalence class are identical from the standpoint of
the logic of the module.
error
See compilation error,
design error, logic error,
run-time error, and syntax error.
Contains the statements that cause the computer to
do something.
executable statement
The basic unit of grammar in C++ consisting of valid
identifiers, standard identifiers, reserved words, numbers, and/or
characters, together with appropriate punctuation.
execute
To carry out the instructions of a program.
exit-controlled loop
See post-test loop.
expert system
A program able to reason as an expert in a limited
domain.
exponential algorithm
An algorithm whose efficiency is dominated by a term
of the form k2.
exponential form
See floating point.
Nested selection where additional if... else statements
are used in the else option. See also nested if statement.
factorial
The product of the first N positive integers (denoted
as N!).
fatal embrace
See deadlock.
The phrase used to describe the number of columns
used for various output. See also formatting.
FIFO
See queue.
file stream
A data structure that consists of a sequence of components
that are accessed by input or output operations.
finite state automata
Algorithms driven by a table indexed by the possible
states that can exist and the possible categories of input symbols
are called finite state 'algorithms. Machines running such algorithms
are finite state automata.
first-in, first-out (FIFO)
See queue.
fixed-repetition loop
A loop used when it is known in advance the number
of times a segment of code needs to be repeated.
A method of writing decimal numbers where the decimal
is placed where it belongs in the number. See ,also floating point.
A method for writing numbers in scientific notation
to accommodate numbers that may have very large or very small
values. See also fixed point.
folding
A method of hashing in cases where the key is not
an integer value. The nonnumeric characters are removed
and the remaining digits are combined to produce an integer value.
A structured loop consisting of an initializer expression,
a termination expression, an update expression, and a statement.
A name, declared and used in a function declaration,
that is replaced by an actual parameter when the function is called.
formal verification
The use of logic to produce a proof of the correctness
of an algorithm.
Designating the desired field width when printing
integers, reals, and character strings. See also field width.
free store
See heap.
friend of a class
The process of making the data members of one class
available to another class.
front pointer
The pointer to the front of a queue.
function
See library function
and user-defined function.
function member
A function declared within a class declaration module.
functional abstraction
The process of considering only what a function is
to do rather than details of the function.
generic abstract data type
An abstract data type whose component types are specified
as parameters. For example, a generic stack ADT could be used
to create stacks of integers as well as stacks of characters.
general list
A collection of data items that are related by their
relative position in the collection.
A set of nodes that is either empty or has a designated
node (called the root) from which descend zero or more subtrees.
generalized nested loops
Loops whose nesting depth is determined at run time
using recursive logic.
An identifier that can be used by the main program
and all subprograms in a program.
global variable
See global identifier.
graph
A set of data elements called nodes and the paths
between them called edges.
halting problem
A problem concerned with determining whether or not
a given program will terminate or loop indefinitely when provided
with a given set of input data.
hardware
The actual computing machine and its support
devices.
The property of one class having an object of another
class as a data member. See also is-a relation.
hashing
A density-dependent search technique whereby the
key for a given data item is transformed using a function to produce
the address where that item is stored in memory.
head pointer
A pointer to the first item in a list.
header file
A C++ file that provides data and function declarations
in a library to client modules.
An area of computer memory where storage for dynamic
data is available. Or: A binary tree with the heap property.
heap property
A binary tree has the heap property when the data
at any given node are greater or equal to the data in its left
and right subtrees.
A sort in which the array is treated like an array
implementation of a binary tree. The items are repeatedly manipulated
to create a heap from which the root is removed and added to the
sorted portion of the array. See also bubble sort,
insertion sort, merge sort,
quick sort, radix sort,
selection sort, and shell sort.
height balancing
A technique for ensuring that an ordered binary tree
remains as full as possible in form.
heuristics
Rules of thumb that cut down on the number of possible
choices to examine. They often lead to quick solutions but do
not guarantee a solution the way an algorithm does.
hierarchy
A relation between nodes whereby one is viewed as
above or prior to another.
high-level language
Any programming language that uses words and symbols
to make it relatively easy to read and write a program. See
also assembly language
and machine language.
Words that must be created according to a well-defined
set of rules but can have any meaning subject to these rules.
See also library identifiers.
implementation file
A C++ file that provides the implementations of data
and functions declared in a header file.
index
See array index
or loop index.
indexed sequential access method (ISAM)
The most common method of indexed sequential search.
indexed sequential search
Use of a partial index based on disk-dependent factors
to find the proper portion of the disk for sequential searching
for a key.
index sort
Sorting an array by ordering the indices of the components
rather than exchanging the components.
Inductive assertion
A method of formally proving the correctness of an
algorithm by using an inductive proof.
infinite loop
A loop in which the controlling condition is not
changed in such a manner to allow the loop to terminate.
infix
Algebraic notation in which the operator appears
between the two operands to which it will be applied.
infix priority
A function that ranks the algebraic operators in
terms of their precedence.
information hiding
The process of suppressing the implementation details
of a function or data structure so as to simplify its use in programming.
The process by which a derived class can reuse attributes
and behavior defined in a base class. See also base class
and derived class.
inorder predecessor
The node preceding a given node in an inorder traversal.
inorder successor
The node following a given node in an inorder traversal.
inorder threads
Pointers to the inorder predecessor and successor
of a node.
inorder traversal
A binary tree traversal in which a node's left subtree
is visited first, then that node is processed, and finally the
node's right subtree is visited.
input
Data obtained by a program during its execution.
input assertion
A precondition for a loop.
A device that provides information to the computer.
Typical devices are keyboards, disk drives, card readers, and
tape drives. See also I/O device and output device.
insertion rule
For binary trees, a rule whereby a new item is placed
in the left subtree of an item greater than it or in the right
subtree of an item less than it.
Sorts an array of elements that starts with an empty
array and inserts elements one at a time in their proper order.
See also bubble sort,
heap sort, merge sort,
quick sort, radix sort,
selection sort, and shell sort.
instance
A computational object bearing the attributes and
behavior specified by a class.
integer arithmetic operations
Operations allowed, on data of type int. This
includes the operations of addition, subtraction, multiplication,
division, and modulus to produce integer answers.
interface
A formal statement of how communication occurs between
subprograms, the main driver, and other subprograms.
invariant expression
An assertion that is true before the loop and after
each iteration of the loop.
invoke
See call.
Any device that allows information to be transmitted
to or from a computer. See also input device and
output device.
The property of one class being a derived class of
another class. See also has-a relation,
derived class, and base class.
iteration
See loops.
key
A field in a data structure that is used to access
an element in that structure.
key-to-address transformation
A transformation in which the key of a data item
maps to the address at which the data are stored.
keywords
Either reserved words or library identifiers.
last-in, first-out (LIFO)
See stack.
leaf
In a tree, a node that has no children.
level
All nodes in a tree with a path of the same length
from the root node.
lexical analysis
The task of recognizing valid words or tokens in
an input stream of characters.
l-value
A computational object capable of being the target
of an assignment statement.
library constant
A constant with a standard meaning, such as NULL
or INT-MAX, available in most versions of C++.
A function available in most versions of C++. A list
of useful C++ library functions is set forth in Appendix 2.
Words defined in standard C++ libraries. See also
identifiers.
LIFO
See stack.
linear algorithm
A Polynomial algorithm in which the highest nonzero
term is n.
linear collision processing
Method of handling a collision in which the storage
space is searched sequentially from the location of the collision
for an available location where the new key can be placed.
linear ordering
Any ordering of data in which there is an identifiable
first element, second element, and so forth.
linear representation (of binary tree)
An implementation of a binary tree in an array. For
a given node stored at index position K that node's left child
is at position 2K, and the right child is at position 2K+ 1.
linear search
See sequential search.
linked collision processing
Method of handling a collision in which the second
key is stored in a linked list located in an overflow area.
linked list
A list of data items where each item is linked to
the next one by means of a pointer.
linked representation
An implementation of a binary tree in which pointer
fields are used to reference the right and left child of a node
in the tree (as opposed to the linear representation of a binary
tree).
LISP (LIST Processor)
A highly-recursive computer programming language
used heavily in artificial intelligence (AI).
list traversal
The process of sequentially visiting each node in
a list.
An identifier that is restricted to use within a
subblock of a program.
local variable
See local identifier.
logarithmic algorithm
An algorithm whose efficiency is dominated by a term
of the form logn.
See design error.
logical operator
Either logical connective (&, ||) or negation
(!).
logical order
An ordering of data items according to some defined
criterion such as alphabetic, increasing numeric, and so forth.
That logical order of the data may or may not be the physical
order of the data as stored in the computer.
logical size
The number of data items actually available in a
data structure at a given time. See also physical size.
logically sorted
Data have been logically sorted when pointers to
the data have been sorted, even though the data itself have not
been touched. Hence, items that the sort places consecutively
need not be physically adjacent.
log2n search algorithm
A search algorithm whose efficiency is dominated
by a term of the form log2n.
Variable used for control values in a loop.
loop invariant
An assertion that expresses a relationship between
variables that remains constant throughout all iterations of the
loop.
loop variant
An assertion whose truth changes between the first
and final execution of the loop.
loop verification
The process of guaranteeing that a loop performs
its intended task.
Program statements that cause a process to be repeated.
See also for loop,
do ... while and while loop.
low-level language
See assembly language.
The language used directly by the computer in all
its calculations and processing.
main block
The main part of a program.
main driver
The main program when subprograms are used to accomplish
specific tasks. See also executable section.
Memory contained in the computer. See also memory
and secondary memory.
main unit
A computer's main unit contains the central processing
unit (CPU) and the main (primary) memory; it is hooked to an input
device and an output device.
Large computers typically used by major companies
and universities. See also microcomputer and minicomputer.
maintenance phase
The fifth phase of the software system life cycle.
In this phase, changes must be made in the original program either
to fix errors discovered by the users of the program or to meet
new user needs.
manifest interface
The property of a function such that, when the function
is called, the reader of the code can tell clearly what information
is being transmitted to it and what information is being returned
from it.
mapping function
A function that transforms row-column array coordinates
to the linear address of that array entry.
The ordered sequence of storage cells that can be
accessed by address. Instructions and variables of an executing
program are temporarily held here. See also main memory
and secondary memory.
memory location
A storage cell that can be accessed by address.
See also memory.
merge
The process of combining lists. Typically refers
to files or arrays.
Sort in which the array is repeatedly split in half
and then these pieces are merged together. See also bubble sort,
heap sort, insertion sort,
quick sort, radix sort,
selection sort, and shell sort.
message
In object-oriented programming, a signal to perform
an operation on an object.
message-passing
In object-oriented programming, one object's telling
another object to perform an operation that is part of its encapsulation.
method of inductive assertions
Method of formally verifying the correctness of an
algorithm by identifying the input assertions, output assertions,
and loop invariants of the algorithm and constructing a verification
proof by mathematical induction.
A computer capable of fitting on a laptop or desktop,
generally used by one person at a time. See also mainframe
and minicomputer.
A small version of a mainframe computer. It is usually
used by several people at once. See also mainframe and
microcomputer.
mixed-mode
Expressions containing data of different types; the values of these expressions will be of either type, depending on the rules for evaluating them.
The process of developing an algorithm using modules.
See also module.
modularity
The property possessed by a program that is written
using modules.
An independent unit that is part of a larger development.
Can be a function or a class (set of functions and related data).
See also modular development.
module specifications
In the case of a function, a description of data
received, information returned, and task performed by a module.
In the case of a class, a description of the attributes and behavior.
modular structure chart
A graphic tool used by software designers to display
the hierarchical relationships among the modules of the software
system.
modular testing
A method of testing in which each module is tested
immediately after it has been completed rather than when the entire
system has been completed.
multilinked list
A linked list in which each node has two or more
link fields.
natural language
A language by which humans normally communicate (such
as English), as opposed to a formal programming language (such
as C++).
negation
The use of the logical operator ! to negate the Boolean
value of an expression.
A selection statement used within another selection
statement. See also extended if statement.
nested loop
A loop as one of the statements in the body of another
loop.
nested selection
Any combination of selection statements within selection
statements. See also selection statement.
network
A graph in which the edges have weight values associated
with them.
node
One data item in a linked list.
null character
The special character ('\O') used to mark the end
of a string in C++.
null statement
See empty statement.
numerical analysis
A field concerned with obtaining numerical answers
to mathematical problems which involve much computation.
object code
See object program.
object-oriented programming
A programming paradigm in which a data object is
viewed as the owner of operations, as opposed to procedural programming
in which an operation is passed data objects as actual parameters.
Object-oriented programming emphasizes the ADT approach and allows
the users of an ADT to extend the operations of an ADT library
in a convenient and efficient fashion.
The machine code version of the source program.
one-key table
A set of values each of which is accessed by specifying
a unique key value, where the key values are ordered.
Positions an input stream pointer at the beginning
of a file for the purpose of reading from the file.
Positions an output stream pointer at the beginning
of a file for the purpose of writing to the file.
opening a file
Positions a pointer at the beginning of a file.
See also opened for reading and opened for writing.
operating system
A large program that allows the user to communicate
with the hardware and performs various management tasks.
order of magnitude
Power of ten. Two numbers have the same order of
magnitude if their representations in scientific notation have
identical exponents to designate the power of ten.
A data structure that supports indexing for retrieval
or change of data items, the detection of the logical size of
the structure, and addition or removal of data items from the
logical end of the structure.
ordering
A means of arranging the elements in a list.
ordering property
In a binary tree, the data in each node of the tree
are greater than or equal to all of the data in that node's left
subtree and less than or equal to all of the data in its right
subtree.
ordinal data type
A data type ordered in some association with the
integers; each integer is the ordinal of its associated character.
output
Information that is produced by a program.
output assertion
A postcondition for a loop.
A device that allows you to see the results of a
program. Typically it is a monitor or printer. See also input device and I/0 device.
In arithmetic operations, a value may be too large
for the computer's memory location. A meaningless value may be
assigned or an error message may result. See also underflow.
The process of using the same operator symbol or identifier to refer to many different functions.
See also polymorphism.
parallel arrays
Arrays of the same length but with different component
data types.
parallel processing
The use of more than one processor to execute parts
of a program concurrently. The effect is that these parts are
completed in parallel rather than in sequence.
parameter
See argument.
parameter list
A list of parameters. An actual parameter list is
contained in the function call. A formal parameter list is contained
in the function declaration and heading.
parent
In a tree, the node that is pointing to its children.
Tree representation of the syntactic structure of
a source program produced by a compiler. Also referred to as abstract
syntax tree.
parser
A program that checks the syntax of an expression
and represents that expression in a unique form.
parser generator
A program that can take the input grammar for a language
and produce the parser for that language.
parsing
The procedure of checking the syntax of an expression
and representing it in one unique form.
partition
In quick sort, the process of moving the pivot to
the location where it belongs in the sorted array and arranging
the remaining data items to the left of the pivot if they are
less than or equal to the pivot and to the right if they are greater
than the pivot.
passed by reference
When the address of the actual parameter is passed
to a subprogram.
passed by value
When a copy of the value of the actual parameter
is passed to a subprogram.
path
A sequence of edges which connect two nodes in a
graph or network.
peripheral memory
See secondary memoryand memory.
permutation
An ordered arrangement of the first n positive
integers in which each integer appears exactly once.
The number of memory units available for storing
data items in a data structure. See also logical size.
pivot
Item used to direct the partitioning in quick sort.
pointer
A memory location containing the location of another
data item.
pointer sort
A sort in which pointers to the data are manipulated
rather than the data itself.
Frequently designated as ptr, a pointer variable
is a variable that contains the address of a memory location.
See also address
and dynamic memory.
The property of one operator symbol or function identifier
having many meanings. See also overloading.
polynomial algorithm
An algorithm whose efficiency can be expressed in
terms of a polynomial.
postcondition
An assertion written after a segment of code.
postfix
Unambiguous algebraic notation in which the s arithmetic
operator appears after the two operands upon which it is to be
applied.
postorder traversal
A binary tree traversal in which at any node, that
node's left subtree is visited first, then that node's right subtree
is visited, and finally that node is processed.
A loop where the control condition is tested after
the loop is executed. do . . . while loop is a post-test
loop. Also referred to as an exit-controlled loop.
precondition
An assertion written before a particular statement.
prefix
Unambiguous algebraic notation in which the arithmetic
operator appears before the two operands upon which it is to be
applied.
preorder traversal
A binary tree traversal in which at any node, that
node is first processed, then that node's left subtree is visited,
and finally that node's right subtree is visited.
pretest condition
A condition that controls whether the body of the
loop is executed before going through the loop.
A loop where the control condition is tested before
the loop is executed. A while loop is a pretest loop. Also
referred to as an entrance-controlled loop.
primary memory
See main memory and
memory.
prime hash area
In linked collision processing, the main storage
area in which keys are placed if no collision occurs.
priority queue
A queue in which the entries on the queue are ranked
into groups according to priority. Such a queue requires a rear
pointer for each different possible priority value.
A data member or member function that is accessible
only within the scope of a class declaration.
profile an algorithm
A means of empirically measuring the execution of
an algorithm by inserting counters to keep track of the number
of times certain instructions are executed during a run of the
program.
program
A set of instructions that tells the machine (the
hardware) what to do.
program heading
The heading of the main block of any C++ program;
it must contain the identifier main.
program proof
An analysis of a program that attempts to verify
the correctness of program results.
A method of using selection statements to guard against
unexpected results.
The process of carefully following, using pencil
and paper, steps the computer uses to solve the problem given
in a program. Also referred to as a trace.
programming language
Formal language that computer scientists use to give
instructions to the computer.
prompt
A message or marker on the terminal screen that requests
input data.
proportional
Term applied to two algebraic functions whose quotient
is a constant.
A data member or member function that is accessible
only within the scope of a class declaration or within the class
declaration of a derived class.
protection
See program protection.
pseudocode
A stylized half-English, half-code language written
in English but suggesting C++ code.
A data member or member function that is accessible
to any program component that uses the class.
quadratic algorithm
A polynomial algorithm in which the highest nonzero
term is n2.
quadratic collision processing
Method of handling a collision in which the storage
space is searched in the k2 place, for successive
integer values of k starting at the location of the collision,
until an available spot is found.
A dynamic data structure where elements are entered at one end and removed from the other end. Referred to as a FIFO (first-in, first-out) structure.
A relatively fast sorting technique that uses recursion.
See also bubble sort,
heap sort, insertion sort,
merge sort, radix sort,
selection sort, and shell sort.
r-value
A computational object capable of being assigned
to a variable.
Sorts integer data by repeatedly placing the items
into bins and then collecting the bins, starting with the least
significant digit for the first pass and finishing with the most
significant digit. Also referred to as bin sort. See also bubble sort,
heap sort, insertion sort,
merge sort, quick sort,
selection sort, and shell sort.
random access
Ability to access any elements in a list without
first accessing all preceding elements.
random access file
A file whose components can. be accessed using random
access.
random number generator
A function that returns a number in a given range
each time it is called. The numbers it returns are statistically
random in that after repeated calls to the function, the sequence
of numbers returned is evenly distributed over the interval yet
each one is completely unpredictable.
randomized storage
A name given to list access via a hashing function.
range bound error
The situation that occurs when an attempt is made
to use an array index value that is less than 0 or greater than
or equal to the size of the array.
reading from a file
Retrieving data from a file.
ready queue
In an operating system, the queue of processes with
cleared access to all the resources the processes require to run.
real arithmetic operations
Operations allowed on data of type float. This includes
addition, subtraction, multiplication, and division.
rear pointer
The pointer to the rear of a queue.
receiver object
A computational object to which a request is sent
for a service.
The process of a subprogram calling itself A clearly
defined stopping state must exist. Any recursive subprogram can
be rewritten using iteration.
recursive step
A step in recursive process that solves a similar
problem of smaller size and eventually leads to a termination
of the process.
recursive subprogram
See recursion.
reference parameter
A formal parameter that requires the address of the
actual parameter to be passed to a subprogram. The value of the
actual parameter can be changed within the subprogram.
rehashing
Method of handling a collision in which a sequence
of new hashing functions is applied to the key that caused the
collision until an available location for that key is found.
rehashing collision processing
Resolving a collision by invoking a sequence of hashing
functions on a key.
relational operator
An operator used for comparison of data items of
the same type.
relative ordering
Ordering imposed on the entries in a list by their
relative positions in that list.
relatively prime
Two numbers are relatively prime if and only if their
only common factor is 1.
repetition
See loops.
reserved words
Words that have predefined meanings that cannot be
changed. They are highlighted in text by capital boldface print;
a list of C++ reserved words is given in Appendix 1.
return type
The type of value returned by a function.
robust
The state in which a program is protected against
most possible crashes from bad data and unexpected values.
root
The first or top node in a tree.
A means of traversing a two-dimensional array whereby
all of the data in one row are accessed before the data in the
next row. See also column-major order.
Error detected when, after compilation is completed,
an error message results instead of the correct output. See
also compilation error,
design error, logic error,
and syntax error.
scope of identifier
The largest block in which the identifier is available.
An auxiliary device for memory, usually a disk or
magnetic tape. See also main memory and memory.
sector
A particular portion of a magnetic disk used at the
machine language level in addressing information stored on the
disk.
seed
A global number used as the basis for generating
random numbers in random number generating function.
A sorting algorithm that sorts the components of
an array in either ascending or descending order. This process
puts the smallest or largest element in the top position and repeats
the process on the remaining array components. See also bubble sort,
heap sort, insertion sort,
merge sort, quick sort,
radix sort, and shell sort.
A control statement that selects some particular
logical path based on the value of an expression. Also referred
to as a conditional statement.
self-documenting code
Code that is written using descriptive identifiers.
semantics
The semantics of an algorithmic statement is the
action dictated by that statement.
semaphore
In an operating system, special flags that regulate
the addition and removal of processes to and from the blocked
and ready queues.
sender
A computational object that requests a service from
another computational object.
sentinel value
A special value that indicates the end of a set of
data or of a process.
sequential access
Requirement that elements of a list must be accessed
according to the list's ordering so that before a particular element
can be accessed, all preceding elements must be accessed first.
sequential access file
A file whose components must be accessed using sequential
access.
sequential algorithm
The process of searching a list by examining the
first component and then examining successive components in the
order in which they occur. Also referred to as linear search.
server
A computational object that provides a service to
another computational object.
shaker sort
A variation on the bubble sort in which each pass
through the data positions the (current) largest element in the
(current) last array index and the (current) smallest element
in the (current) first array index.
Sort that works by dividing the array into smaller,
noncontiguous segments. These segments are separately sorted using
the insertion sort algorithm. The number of these segments is
repeatedly reduced on each successive pass until the entire array
has been sorted. See also bubble sort,
heap sort, insertion sort,
merge sort, quick sort,
radix sort, and selection sort.
shift folding
A variation on folding in which each numeric part
of the key is treated as a separate number, and these numbers
are added to form an integer value. See also boundary folding.
short-circuit evaluation
The process whereby a compound Boolean expression
halts evaluation and returns the value of the first subexpression
that evaluates to TRUE, in the case of ||, or FALSE, in the case
of &&.
siblings
The child nodes of a given node.
side effect
A change in a variable, which is the result of some
action taken in a program, usually from within a function.
sieve of Eratosthenes
A technique devised by the Greek mathematician Eratosthenes
for finding all prime numbers greater than 2 and less than or
equal to a given number.
An expression where two numbers or variable values
are compared using a single relational operator. See also Boolean expression
and compound Boolean expression.
simulation
A computer model of a real-life situation.
simulation of system stack
Technique used to eliminate recursion by making a
program explicitly perform the duties of the system stack.
software
Programs that make the machine (the hardware) do
something, such as word processing, database management, or games.
software engineering
The process of developing and maintaining large software
systems.
software reuse
The process of building and maintaining software
systems out of existing software components.
software system life cycle
The process of development, maintenance, and demise
of a software system. Phases include analysis, design, coding,
testing/verification, maintenance, and obsolescence.
sort-merge
The process of repeatedly subdividing a long list,
sorting shorter lists, and then merging to obtain a single sorted
list.
sorted collection
A derived class of ordered collection, in which the
data items are maintained in ascending or descending order. See
also ordered collection.
source program
A program written by a programmer. See also system software.
sparse table
A table in which a high percentage of data storage
locations will be of one uniform value.
A dynamic data structure where access can be made
from only one end. Referred to as a LIFO (last-in, first-out)
structure.
stack priority
Function to hierarchically rank algebraic operators
in order of precedence.
standard simple types
Predefined data types such as int, float,
and char.
state space
The space of all possible states which can be generated
in the solution to a given problem.
state-transition diagram
A diagram used to model the logic of a finite state
machine.
The process of repeatedly subdividing tasks into
subtasks until each subtask is easily accomplished. See also
structured programming and top-down design.
stopping state
The well-defined termination of a recursive process.
Also called sequential algorithm, this algorithm
consists of a sequence of simple tasks.
string
An abbreviated name for a string literal.
string literal
One or more characters, enclosed in double quotes,
used as a constant in a program.
string data type
A data type that permits a sequence of characters.
In C++, this can be implemented using an array of characters.
structure chart
A graphic method of indicating the relationship between
modules when designing the solution to a problem.
structured design
A method of designing software by specifying ' modules
and the flow of data among them.
Programming that parallels a solution to a problem
achieved by top-down design. See also stepwise refinement and top-down design.
stub programming
The process of using incomplete functions to test
data transmission among them.
subblock
A block structure for a subprogram. See also block.
subprogram
A program within a program. Functions are subprograms.
subscript
See array index or loop index.
subtree
A subset of a tree that is itself a tree.
symbol table
A list of identifiers maintained by a compiler as
it parses a source program.
synonyms
Two keys that hash to the same position and therefore
cause a collision.
syntax
The formal rules governing construction of valid
statements.
syntax diagramming
A method to formally describe the legal syntax of
language structures; syntax diagrams are set forth in Appendix
3.
An error in spelling, punctuation, or placement of
certain key symbols in a program. See also compilation error,
design error, logic error,
and run-time error.
The programs that allow users to write and execute
other programs, including operating systems such as DOS.
system testing
Exercising the interfaces between modules instead
of the logic of a particular module.
systems analyst
The person responsible for analyzing the needs of
the users and then formally specifying the system and its requirements
to meet those needs.
tail-recursive
The property that a recursive algorithm has of performing
no work after each recursive step. See also recursion.
test cases
Collection of sets of test data that will exercise
all the logical possibilities the module will encounter. Each
test case has a corresponding expected result called the test
oracle.
test oracle
The expected result for a particular test case when
a module is being tested.
testing phase
The fourth phase of the software system life cycle.
In this phase, the program code is thoroughly tested in an effort
to discover errors both in the design of the program and in the
code itself.
test program
A short program written to provide an answer to a
specific question.
thread
A pointer contained in a tree node which leads to
the predecessor or successor of the node relative to a specified
traversal.
threaded tree
A tree in which threading is used.
threading
A technique of avoiding recursion in tree traversal
algorithms whereby the pointers unused in tree formation are turned
into pointers to the inorder predecessor and inorder successor
of that node.
time/space trade-off
The maxim that an attempt to make a program more
efficient in terms of time will only come as a result of a corresponding
decrease in efficiency in terms of space, and vice versa.
token
A language symbol comprised of one or more characters
in an incoming stream of characters. The basic unit in lexical
analysis.
A design methodology for solving a problem whereby
you first state the problem and then proceed to subdivide the
main task into major subtasks. Each subtask is then subdivided
into smaller subtasks. This process is repeated until each remaining
subtask is easily solved. See also stepwise refinement
and structured programming.
trace
See program walk-through.
track
A particular portion of a magnetic disk used at the
machine language level in addressing information stored on the
disk.
tree
See general tree.
tree of recursive calls
tree traversal
A means of processing every node in the tree.
trial-and-error backtracking
Recursion in which more recursive calls may be made
after the first return operation occurs.
trie index
A type of indexing used when the keys are variable-length
character strings. Although taken from the word retrieve, trie
is pronounced "try."
Turing machine
A hypothetical computing machine which consists of
input and output units, and infinite memory in the form of a sequentially
organized tape to store characters from a finite alphabet, a finite
collection of states in which the machine could exist in at any
given time, and a control unit capable of checking and potentially
modifying the contents of any memory cell.
two-dimensional array
An array in which each element is accessed by a reference
to a pair of indices.
two-key table
A set of values each of which is accessed by two
keys, where the set of primary keys is ordered and the set of
secondary keys for each primary key is also ordered.
two-way merge
The process of merging two sorted lists.
type
See data type.
undecidable proposition
A statement within an axiomatic system such that
neither that statement nor its negation can be proven by reasoning
within the system itself
If a value is too small to be represented by a computer,
the value is automatically replaced by zero. See also overflow.
user-defined data type
A new data type introduced and defined by the programmer.
A new function introduced and defined by the programmer.
user-friendly
A phrase used to describe an interactive program
with clear, easy-to-follow messages for the user.
Often called value of a memory location. Refers to
the value of the contents of a memory location. See also address.
value parameter
A formal parameter that is local to a subprogram.
Values of these parameters are not returned to the calling program.
variable
A memory location, referenced by an identifier, whose
value can be changed during a program.
variable condition loop
A repetition statement in which the loop control
condition changes within the body of the loop
variable declaration section
The section of the declaration section where program
variables are declared for subsequent use.
vertex
A data object (or node) in a graph.
volatile list
A list that undergoes frequent insertions and deletions.
weight
The numeric value associated with an edge in a network.
A pretest loop examining a Boolean expression before
causing a statement to be executed.
The method of testing a module in which the tester
is aware of the method of implementation and internal logic of
that module. See also black box testing.
A unit of memory consisting of one or more bytes.
Words can be addressed.
The arrangement of data items prior to the beginning
of the sort procedure which causes that procedure to take the
longest amount of time for that particular set of items. See
also best case.
writing to a file
The process of entering data to a file.