CSE131 Glossary of Terms
This is a partial list of terms used in CSE131. If you think an
important term is missing, please let us know.
- abstraction
- a mechanism for hiding detail
-
abstract data type (ADT)
-
an interface and its associated expected behavior,
usually implemented as an object containing
some data (the internal representation) and a set of methods implementing the interface
-
abstraction barrier (or interface)
-
a set of operations (or methods of an object) that is used
to access and/or operate on the internal representation
- accessor
- a method for extracting information from an object
-
activation record
-
holds the information on the call stack
that is needed for one procedure call
- actual parameter
- the values that are passed into a procedure or method
-
address
-
a location in memory; each data item is stored at a particular
memory address
- algorithm
- the idea of how to carry out a computation, may be
implemented as a procedure
- base case
- the simplest case, usually the termination case for a recursive algorithm
- binary search tree
- a data structure with in which every node refers to a
left subtree and a right subtree such that all values in
the left subtree are smaller than the value in the node
and all elements in the
right subtree are greater than (or equal to) the value in
the node. the top node is called the root.
the nodes with no children (left and right subtrees empty)
are called leaves.
- binding
- the relation between a symbol and its value
- black box
- something that can be used without knowing how it works inside
-
call stack (or execution stack)
-
the part of memory containing the bindings
of formal parameters to actual values for procedure calls
- circular list
- a linked list in which the rear item refers back to
the head item
-
class
-
a definition of a type of object
- compound data
- a collection of data treated as a single unit; has a constructor, accessors,
and an identifier
- constructor
- a method used to create a new object
-
correctness
-
safety plus liveness
- data
- information that is manipulated by a computation
-
data abstraction
-
a method for providing a natural, high-level semantics
for (a collection of) data while supressing the details of the
internal representation
- data flow model
- a model of computation in which each computational component is represented as a box whose
arguments and results may be connected from and to other boxes
- encapsulation
- a mechanism for hiding and protecting information
- environment
- a "place" in which expressions are evaluated, usually with an associated
set of bindings
-
execution stack
-
(see call stack)
- expression tree
- a diagram showing the operators and operands of an expression
- formal parameter
- the parameters declared for a method or procedure,
into which the actual parameter values will be copied
-
garbage
-
memory that had been allocated but is no longer reachable by a process
-
garbage collection
-
claiming unreachable storage for reuse
-
heap
-
an area of memory from which space for dyanamic structures
are allocated
- infix notation
- a notation in which operators appear between the operands, as in
3 + 5
-
instance variables
-
the variables holding the internal representation of an object
-
interface
-
(see abstraction barrier)
-
internal representation
-
the data representation (stored in the instance variables) of an object
- iteration
- a repeated computation, usually performed on a range of
values or on the elements of a data structure
- iterator
- an object that contains a reference to internal items of a
data structure in order to support iterating over the data in those
items without exposing the internal representation of the structure itself
- linked list
- a data structure consisting of a sequence of values linked together
in memory by a chain of references
-
liveness
-
the program will eventually provide a result
- loop
- a programming language construct that supports iteration
(for example, a while loop)
-
loop invariant
-
a property of, or relationship among, the values of the loop variables such
that the property is true both
initially and after each iteration of the loop; together with the
termination condition, a loop invariant is useful in demonstrating
the correctness of a loop
-
memory
-
a place in the computer where values are stored for later retreival
-
message-passing
-
a way of thinking about object-oriented programming in which objects
communicate by sending messages to each other (to invoke methods on them)
-
method
-
an operation that one may invoke on an object
-
mutation
-
the act of changing the values of variables or data structures
-
object
-
an abstraction that encapsulates data and knows how to operate
on the data
- parameter
- the way values are passed to a method or procedure
- polymorphism
- treating objects of many types in a uniform way
- predicate
- an expression that evaluates to either true or false
- prefix notation
- a notation in which operators appear before the operands, as in
add(3,5)
- primitive data
- data, such as numbers and symbols, that are built into the language
- procedure
- a description of an activity to be carried out (by a computer)
- process
- an activity (carried out by a computer)
- programming language
- a language used to write a procedure or other description of
a computation
- queue
- a data structure with first-in first-out behavior, supporting
the operations enqueue (to insert) and dequeue (to remove)
- reduction
- a recasting of one problem as another (somewhat different) problem
- recursion
- a reduction of a problem to another (typically smaller) instance of the same problem
-
representation invariant
-
a property that holds true of the internal representation initially
and after the completion of each method
- semantics
- the meaning of an expression
- stack
- a data structure with last-in first-out behavior, supporting
the operations push (to insert) and pop (to remove)
-
state
-
stored information (associated with a process)
- subclass
- a class that extends another class, possibly by adding
new methods or overriding existing methods
- substitution model
- a model of computation in which expressions are successively replaced by their
values until a final result is reached
- symbol
- a name used to denote a value
- syntax
- the notation used to express an idea
- tail recursion
- a form of recursion in which the result of the recursive call is the final answer;
no combining is done on the result of the recursive call
-
termination condition
-
a predicate that becomes true when a computation ends
- top-down refinement
- a design technique in which a problem is described at a highly abstract level and then
broken down into finer and finer details until all the pieces are filled in