Glossary¶

abstract base class¶

A class in which some functions are not implemented. Abstract bases classes cannot be instantiated — a derived class must override the abstract virtual function with an implementation.

abstract data type¶

Abbreviated ADT. The realization of a data type as a software component.

abstraction¶

A technique used to reduce the complexity of systems and data. An abstraction often involves a simplified model of the ‘real world’ for the purposes of achieving goals within a specific problem domain.

Data abstraction enforces a clear separation between the abstract properties of a data type and the concrete details of its implementation.

activation record¶

The entity that is stored on the runtime stack during program execution. It stores any active local variable and the return address from which a new subroutine is being called, so that this information can be recovered when the subroutine terminates.

activecode¶

A unique interpreter environment that allows code to be executed within a web browser.

address¶

A location in memory.

adjacency list¶

An implementation for a graph that uses an (array-based) list to represent the vertices of the graph, and each vertex is in turn represented by a (linked) list of the vertices that are neighbors.

adjacency matrix¶

An implementation for a graph that uses a 2-dimensional array where each row and each column corresponds to a vertex in the graph. A given row and column in the matrix corresponds to an edge from the vertex corresponding to the row to the vertex corresponding to the column.

adjacent¶

Two nodes of a tree or two vertices of a graph are said to be adjacent if they have an edge connecting them. If the edge is directed from $a$ to $b$, then we say that $a$ is adjacent to $b$, and $b$ is adjacent from $a$.

ADT¶

Abbreviation for abstract data type.

adversary argument¶

A type of lower bounds proof for a problem where a (fictional) “adversary” is assumed to control access to an algorithm’s input, and which yields information about that input in such a way that will drive the cost for any proposed algorithm to solve the problem as high as possible. So long as the adversary never gives an answer that conflicts with any previous answer, it is permitted to do whatever necessary to make the algorithm require as much cost as possible.

aggregate type¶

A data type whose members have subparts. For example, a typical database record. Another term for this is composite type.

algorithm¶

A general step by step process for solving a problem.

algorithm analysis¶

to-term:: growth rate :label: key concept
to-term:: upper bound :label: key concept
to-term:: lower bound :label: key concept
to-term:: asymptotic analysis :label: synonym
to-term:: asymptotic algorithm analysis :label: formal synonym

A less formal version of the term asymptotic algorithm analysis, generally used as a synonym for asymptotic analysis.

alphabet trie¶

A trie data structure for storing variable-length strings. Level $i$ of the tree corresponds to the letter in position $i$ of the string. The root will have potential branches on each intial letter of string. Thus, all strings starting with “a” will be stored in the “a” branch of the tree. At the second level, such strings will be separated by branching on the second letter.

ancestor¶

In a tree, for a given node $A$, any node on a path from $A$ up to the root is an ancestor of $A$.

anti-pattern¶

A common response to a recurring problem that is generally ineffective. Anti-patterns represent examples that you should not emulate! As bad as they are, they can still be instructive. Compare to design pattern.

antisymmetric¶

In set notation, relation $R$ is antisymmetric if whenever $aRb$ and $bRa$, then $a = b$, for all $a, b \in \mathbf{S}$.

api¶

API¶

An Application Programming Interface (API) is a set of functions, or classes used by a program. Often an API provides a family of functions or classes that work together to provide a complete set of capabilities.

approximation algorithm¶

An algorthm for an optimization problem that finds a good, but not necessarily cheapest, solution.

array-based list¶

An implementation for the list ADT that uses an array to store the list elements.

array-based queue¶

Analogous to an array-based list, this uses an array to store the elements when implementing the queue ADT.

array-based stack¶

Analogous to an array-based list, this uses an array to store the elements when implementing the stack ADT.

ASCII character coding¶

American Standard Code for Information Interchange. A commonly used method for encoding characters using a binary code. Standard ASCII uses an 8-bit code to represent upper and lower case letters, digits, some punctuation, and some number of non-printing characters (such as carrage return). Now largely replaced by UTF-8 encoding.

assembly code¶

to-term:: intermediate code :label: form of

A form of intermediate code created by a compiler that is easy to convert into the final form that the computer can execute. An assembly language is typically a direct mapping of one or a few instructions that the CPU can execute into a mnemonic form that is relatively easy for a human to read.

assignable¶

A type is assignable if the type can be copy-assigned a new value as the left-hand side of the operation.

References are not assignable because once initialized, they cannot be assigned a new value.

associative container¶

A set of sorted data structures that can be quickly searched. map and set are examples.

asymptotic algorithm analysis¶

A more formal term for asymptotic analysis.

asymptotic analysis¶

to-term:: algorithm analysis :label: synonym
to-term:: asymptotic algorithm analysis :label: formal synonym

A method for estimating the efficiency of an algorithm or computer program by identifying its growth rate. Asymptotic analysis also gives a way to define the inherent difficulty of a problem. We frequently use the term algorithm analysis to mean the same thing.

attribute¶

In object-oriented programming, a synonym for data member.

average case¶

In algorithm analysis, the average of the costs for all problem instances of a given input size $n$. If not all problem instances have equal probability of occurring, then average case must be calculated using a weighted average.

backing storage¶

backing store¶

The underlying storage for an ADT.

bag¶

In set notation, a bag is a collection of elements with no order (like a set), but which allows for duplicate-valued elements (unlike a set). A synonym for multilist.

balanced tree¶

A tree where the subtrees meet some criteria for being balanced. Two possibilities are that the tree is height balanced, or that the tree has a roughly equal number of nodes in each subtree.

base¶

Synonym for radix.

base case¶

In recursion, the base case is the termination condition. This is a simple input or value that can be solved without resorting to a recursive call.

base class¶

In object-oriented programming, a class from which another class inherits. The class that inherits is called a subclass or derived class.

base type¶

The data type for the elements in a set. For example, the set might consist of the integer values 3, 5, and 7. In this example, the base type is integers.

best case¶

In algorithm analysis, the problem instance from among all problem instances for a given input size $n$ that has least cost. Note that the best case is not when $n$ is small, since we are referring to the best from a class of inputs (i.e, we want the best of those inputs of size $n$).

big-O notation¶

big-Oh notation¶

In algorithm analysis, a shorthand notation for describing the upper bound for an algorithm or problem.

binary search¶

A standard recursive algorithm for finding the record with a given key within a sorted list. It runs in $O(\log n)$ time. At each step, look at the middle of the current sublist, and throw away the half of the records whose keys are either too small or too large.

binary tree¶

A non-linear data structure with a set of nodes which is either empty, or else has a root node together two binary trees, called the left and right subtrees, which are disjoint from each other and from the root.

binary trie¶

A binary tree whose structure is that of a trie. Generally this is an implementation for a search tree. This means that the search key values are thought of a binary digits, with the digit in the position corresponding to this a node’s level in the tree indicating a left branch if it is “0”, or a right branch if it is “1”. Examples include the Huffman coding tree and the bintree.

binning¶

In hashing, binning is a type of hash function. Say we are given keys in the range 0 to 999, and have a hash table of size 10. In this case, a possible hash function might simply divide the key value by 100. Thus, all keys in the range 0 to 99 would hash to slot 0, keys 100 to 199 would hash to slot 1, and so on. In other words, this hash function “bins” the first 100 keys to the first slot, the next 100 keys to the second slot, and so on. This approach tends to make the hash function dependent on the distribution of the high-order bits of the keys.

bintree¶

to-term:: flyweight :label: uses

A spatial data structure in the form of binary trie, typically used to store point data in two or more dimensions. Similar to a PR quadtree except that at each level, it splits one dimension in half. Since many leaf nodes of the PR quadtree will contain no data points, implementation often makes use of the flyweight design pattern.

block¶

Defines a scope within a program. A synonym for code block.

boolean variable¶

A variable that takes on one of the two values true and false.

bucket¶

In bucket hashing, a bucket is a sequence of slots in the hash table that are grouped together.

bucket hashing¶

A method of hashing where multiple slots of the hash table are grouped together to form a bucket. The hash function then either hashes to some bucket, or else it hashes to a home slot in the normal way, but this home slot is part of some bucket. Collision resolution is handled first by attempting to find a free position within the same bucket as the home slot. If the bucket if full, then the record is placed in an overflow bucket.

bug¶

An error in a program.

call stack¶

Known also as execution stack. A stack that stores the function call sequence and the return address for each function.

cartesian product¶

For sets, this is another name for the set product.

ceiling¶

Written $\lceil x \rceil$, for real value $x$ the ceiling is the least integer $\geq x$.

child¶

In a tree, the set of nodes directly pointed to by a node $R$ are the children of $R$.

class¶

In the object-oriented programming paradigm an ADT and its implementation together make up a class. An instantiation of a class within a program is termed an object.

class hierarchy¶

In object-oriented programming, a set of classes and their interrelationships. One of the classes is the base class, and the others are derived classes that inherit either directly or indirectly from the base class.

class invariant¶

type invariant¶

invariants¶

A class invariant is an assertion about conditions which must be true in order for a class to remain valid.

client¶

The user of a service.

closed¶

A set is closed over a (binary) operation if, whenever the operation is applied to two members of the set, the result is a member of the set.

closed hashing¶

closed hash system¶

A hash system where all records are stored in slots of the hash table. This is in contrast to an open hash system.

closed-form solution¶

An algebraic equation with the same value as a summation or recurrence relation. The process of replacing the summation or recurrence with its closed-form solution is known as solving the summation or recurrence.

code block¶

Defines a scope within a program. A synonym for block.

code generation¶

A phase in a compiler that transforms intermediate code into the final executable form of the code. More generally, this can refer to the process of turning a parse tree (that determines the correctness of the structure of the program) into actual instructions that the computer can execute.

code optimization¶

to-term:: assembly code :label: changes

A phase in a compiler that makes changes in the code (typically assembly code) with the goal of replacing it with a version of the code that will run faster while performing the same computation.

codelens¶

An interactive environment that allows the user to control the step by step execution of a program

cohesion¶

In object-oriented programming, a term that refers to the degree to which a class has a single well-defined role or responsibility.

collision¶

In a hash system, this refers to the case where two search keys are mapped by the hash function to the same slot in the hash table. This can happen on insertion or search when another record has already been hashed to that slot. In this case, a closed hash system will require a process known as collision resolution to find the location of the desired record.

collision resolution¶

The outcome of a collision resolution policy.

collision resolution policy¶

In hashing, the process of resolving a collision. Specifically in a closed hash system, this is the process of finding the proper position in a hash table that contains the desired record if the hash function did not return the correct position for that record due to a collision with another record.

comment¶

Information in a program that is meant for other programmers (or anyone reading the source code) and has no effect on the execution of the program.

comparable¶

The concept that two objects can be compared to determine if they are equal or not, or to determine which one is greater than the other. In set notation, elements $x$ and $y$ of a set are comparable under a given relation $R$ if either $xRy$ or $yRx$. To be reliably compared for a greater/lesser relationship, the values being compared must belong to a total order. In programming, the property of a data type such that two elements of the type can be compared to determine if they the same (a weaker version), or which of the two is larger (a stronger version).

comparator¶

A function given as a parameter to a method of a library (or alternatively, a parameter for a C++ template or a Java generic). The comparator function concept provides a generic way encapulates the process of performing a comparison between two objects of a specific type. For example, if we want to write a generic sorting routine, that can handle any record type, we can require that the user of the sorting routine pass in a comparator function to define how records in the collection are to be compared.

comparison¶

The act of comparing two keys or records. For many data types, a comparison has constant time cost. For others, such as linked list the cost often increases as the number of elements increases.

compile¶

To translate a program written in a high-level language into a low-level language all at once, in preparation for later execution.

compile-time error¶

Errors detected by the compiler. Compare to runtime error, link error, and semantic error.

compile-time polymorphism¶

Compile-time polymorphism¶

A form of polymorphism known as Overloading. Overloaded methods have the same names, but different signatures as a method available elsewhere in the class. Compare to runtime polymorphism.

compiler¶

A computer program that reads computer programs and converts them into a form that can be directly excecuted by some form of computer. The major phases in a compiler include lexical analysis, syntax analysis, intermediate code generation, code optimization, and code generation. More broadly, a compiler can be viewed as parsing the program to verify that it is syntactically correct, and then doing code generation to convert the hig-level program into something that the computer can execute.

complete binary tree¶

A binary tree where the nodes are filled in row by row, with the bottom row filled in left to right. Due to this requirement, there is only one tree of $n$ nodes for any value of $n$. Since storing the records in an array in row order leads to a simple mapping from a node’s position in the array to its parent, siblings, and children, the array representation is most commonly used to implement the complete binary tree. The heap data structure is a complete binary tree with partial ordering constraints on the node values.

Composite design pattern¶

Given a class hierarchy representing a set of objects, and a container for a collection of objects, the composite design pattern addresses the relationship between the object hierarchy and a bunch of behaviors on the objects. In the composite design, each object is required to implement the collection of behaviors. This is in contrast to the procedural approach where a behavior (such as a tree traversal) is implemented as a method on the object collection (such as a tree). Procedural tree traversal requires that the tree have a method that understands what to do when it encounters any of the object types (internal or leaf nodes) that the tree might contain. The composite approach would have the tree call the “traversal” method on its root node, which then knows how to perform the “traversal” behavior. This might in turn require invoking the traversal method of other objects (in this case, the children of the root).

composite type¶

A type whose members have subparts. For example, a typical database record. Another term for this is aggregate type.

composition¶

Relationships between classes based on usage rather than inheritance, i.e. a HAS-A relationship. For example, some code in class ‘A’ has a reference to some other class ‘B’.

compound type¶

A data type built up from simpler parts. Compare to simple type and composite type.

constant running time¶

constant time¶

The cost of a function whose running time is not related to its input size. In Theta notation, this is traditionally written as $\Theta(1)$.

container¶

container class¶

A data structure that stores a collection of records. Typical examples are arrays and hash tables.

cost¶

The amount of resources that the solution consumes.

cost model¶

In algorithm analysis, a definition for the cost of each basic operation performed by the algorithm, along with a definition for the size of the input. Having these definitions allows us to calculate the cost to run the algorithm on a given input, and from there determine the growth rate of the algorithm. A cost model would be considered “good” if it yields predictions that conform to our understanding of reality.

CPU¶

Acronym for Central Processing Unit, the primary processing device for a computer.

current position¶

A property of some list ADTs, where there is maintained a “current position” state that can be referred to later.

data field¶

In object-oriented programming, a synonym for data member.

data item¶

A piece of information or a record whose value is drawn from a type.

data member¶

The variables that together define the space required by a data item are referred to as data members. Some of the commonly used synonyms include data field, attribute, and instance variable.

data structure¶

The implementation for an ADT.

data type¶

A type together with a collection of operations to manipulate the type.

debugging¶

The process of finding and removing any of the three kinds of programming errors.

decision tree¶

A theoretical construct for modeling the behavior of algorithms. Each point at which the algorithm makes a decision (such as an if statement) is modeled by a branch in the tree that represents the algorithms behavior. Decision trees can be used in lower bounds proofs, such as the proof that sorting requires $\Omega(n \log n)$ comparisons in the worst case.

declaration¶

A declaration introduces a new name and type into a scope.

depth¶

The depth of a node $M$ in a tree is the length of the path from the root of the tree to $M$.

depth-first search¶

to-term:: DFS :label: abbreviation
to-term:: depth-first search tree :label: generates

A graph traversal algorithm. Whenever a $v$ is visited during the traversal, DFS will recursively visit all of $v$ ‘s unvisited neighbors.

depth-first search tree¶

A tree that can be defined by the operation of a depth-first search (DFS) on a graph. This tree would consist of the nodes of the graph and a subset of the edges of the graph that was followed during the DFS.

dequeue¶

A specialized term used to indicate removing an element from a queue.

derivation¶

In formal languages, the process of executing a series of production rules from a grammar. A typical example of a derivation would be the series of productions executed to go from the start symbol to a given string.

derived class¶

In object-oriented programming, any class within a class hierarchy that inherits from some other class. A synonym for derived class.

descendant¶

In a tree, the set of all nodes that have a node $A$ as an ancestor are the descendants of $A$. In other words, all of the nodes that can be reached from $A$ by progressing downwards in tree. Another way to say it is: The children of $A$, their children, and so on.

deserialization¶

The process of returning a serialized representation for a data structure back to its original in-memory form.

design pattern¶

An abstraction for describing the design of programs, that is, the interactions of objects and classes. Experienced software designers learn and reuse patterns for combining software components, and design patterns allow this design knowledge to be passed on to new programmers more quickly. Examples are Composite design pattern, flyweight, iterator, strategy, and visitor.

dictionary¶

An abstract data type or interface for a data structure or software subsystem that supports insertion, search, and deletion of records.

discriminator¶

A part of a multi-dimensional search key. Certain tree data structures such as the bintree and the kd tree operate by making branching decisions at nodes of the tree based on a single attribute of the multi-dimensional key, with the attribute determined by the level of the node in the tree.

For example, in 2 dimensions, nodes at the odd levels in the tree might branch based on the $x$ value of a coordinate, while at the even levels the tree would branch based on the $y$ value of the coordinate. Thus, the $x$ coordinate is the discriminator for the odd levels, while the $y$ coordinate is the discriminator for the even levels.

disjoint¶

Two parts of a data structure or two collections with no objects in common are disjoint. This term is often used in conjunction with a data structure that has nodes (such as a tree). Also used in the context of sets, where two subsets are disjoint if they share no elements.

disjoint sets¶

A collection of sets, any pair of which share no elements in common. A collection of disjoint sets partitions some objects such that every object is in exactly one of the disjoint sets.

divide and conquer¶

A technique for designing algorithms where a solution is found by breaking the problem into smaller (similar) subproblems, solving the subproblems, then combining the subproblem solutions to form the solution to the original problem. This process is often implemented using recursion.

divide-and-conquer recurrences¶

A common form of recurrence relation that have the form

\[{\bf T}(n) = a{\bf T}(n/b) + cn^k; \quad {\bf T}(1) = c\]

where $a$, $b$, $c$, and $k$ are constants. In general, this recurrence describes a problem of size $n$ divided into $a$ subproblems of size $n/b$, while $cn^k$ is the amount of work necessary to combine the partial solutions.

domain¶

The set of possible inputs to a function.

double hashing¶

A collision resolution method. A second hash function is used to generate a value $c$ on the key. That value is then used by this key as the step size in linear probing by steps. Since different keys use different step sizes (as generated by the second hash function), this process avoids the clustering caused by standard linear probing by steps.

doubly linked list¶

A linked list implementation variant where each list node contains access pointers to both the previous element and the next element on the list.

dynamic array¶

Arrays, once allocated, are of fixed size. A dynamic array puts an interface around the array so as to appear to allow the array to grow and shrink in size as necessary. Typically this is done by allocating a new copy, copying the contents of the old array, and then returning the old array to free store. In some programming languages, the term vector is used as a synonym for dynamic array.

dynamic memory allocation¶

A programming technique where linked objects in a data structure are created from free store as needed. When no longer needed, the object is either returned to free store or left as garbage, depending on the programming language.

edge¶

The connection that links two nodes in a tree, linked list, or graph.

element¶

One value or member in a set.

empty¶

For a container class, the state of containing no elements.

encapsulation¶

In programming, the concept of hiding implementation details from the user of an ADT, and protecting data members of an object from outside access.

enqueue¶

A specialized term used to indicate inserting an element onto a queue.

enumeration¶

The process by which a traversal lists every object in the container exactly once. Thus, a traversal that prints the nodes is said to enumerate the nodes. An enumeration can also refer to the actual listing that is produced by the traversal (as well as the process that created that listing).

equivalence class¶

An equivalence relation can be used to partition a set into equivalence classes.

equivalence relation¶

Relation $R$ is an equivalence relation on set $\mathbf{S}$ if it is reflexive, symmetric, and transitive.

exception¶

Another name for a runtime error.

exchange¶

A swap of adjacent records in an array.

executable¶

Another name for object code that is ready to be executed.

exponential growth rate¶

A growth rate function where $n$ (the input size) appears in the exponent. For example, $2^n$.

external fragmentation¶

A condition that arises when a series of memory requests result in lots of small free blocks, no one of which is useful for servicing typical requests.

external sort¶

A sorting algorithm that is applied to data stored outside the program, such as a disk file. This is in contrast to an internal sort that is meant to work on data stored in memory.

FIFO¶

Abbreviation for “first-in, first-out”. This is the access paradigm for a queue, and an old terminolgy for the queue is “FIFO list”.

fixed-length coding¶

Given a collection of objects, a fixed-length coding scheme assigns a code to each object in the collection using codes that are all of the same length. Standard ASCII and Unicode representations for characters are both examples of fixed-length coding schemes. This is in contrast to variable-length coding.

floor¶

Written $\lfloor x \rfloor$, for real value $x$ the floor is the greatest integer $\leq x$.

flyweight¶

A design pattern that is meant to solve the following problem: You have an application with many objects. Some of these objects are identical in the information that they contain, and the role that they play. But they must be reached from various places, and conceptually they really are distinct objects. Because there is so much duplication of the same information, we want to reduce memory cost by sharing that space. For example, in document layout, the letter “C” might be represented by an object that describes that character’s strokes and bounding box. However, we do not want to create a separate “C” object everywhere in the document that a “C” appears. The solution is to allocate a single copy of the shared representation for “C” objects. Then, every place in the document that needs a “C” in a given font, size, and typeface will reference this single copy. The various instances of references to a specific form of “C” are called flyweights.

folding method¶

In hashing, an approach to implementing a hash function. Most typically used when the key is a string, the folding method breaks the string into pieces (perhaps each letter is a piece, or a small series of letters is a piece), converts the letter(s) to an integer value (typically by using its underlying encoding value), and summing up the pieces.

free block¶

A block of unused space in a memory pool.

free block list¶

In a memory manager, the list that stores the necessary information about the current free blocks. Generally, this is done with some sort of linked list, where each node of the linked list indicates the start position and length of the free block in the memory pool.

free store¶

Space available to a program during runtime to be used for dynamic memory allocation of objects. The free store is distinct from the runtime stack. The free store is sometimes referred to as the heap, which can be confusing because heap more often refers to a specific data structure. Most programming languages provide functions to allocate (and maybe to deallocate) objects from the free store, such as new in C++ and Java.

full tree¶

A binary tree is full if every node is either a leaf node or else it is an internal node with two non-empty children.

function¶

In programming, a subroutine that takes input parameters and uses them to compute and return a value. In this case, it is usually considered bad practice for a function to change any global variables (doing so is called a side effect).

fundamental type¶

One of the simple types provided by the language. Examples are bool, char, int, and double. Types provided by the STL, such as std::string and std::vector are not considered ‘fundamental’ types.

garbage¶

In memory management, any memory that was previously (dynamically) allocated by the program during runtime, but which is no longer accessible since all pointers to the memory have been deleted or overwritten. In some languages, garbage can be recovered by garbage collection. In languages such as C and C++ that do not provide built-in garbage collection, so creating garbage is considered a memory leak.

garbage collection¶

Languages with garbage collection such Java, JavaScript, Lisp, and Scheme will periodically reclaim garbage and return it to free store.

general tree¶

A tree in which any given node can have any number of children. This is in contrast to, for example, a binary tree where each node has a fixed number of children (some of which might be null). General tree nodes tend to be harder to implement for this reason.

generic programming¶

A computer programming style in which functions are written using placeholders for types. In C++ this is accomplished using :term:templates<template>`. Templates are used to create actual functions for specific types as needed.

grammar¶

A formal definition for what strings make up a language, in terms of a set of production rules.

graph¶

A graph $\mathbf{G} = (\mathbf{V}, \mathbf{E})$ consists of a set of vertices $\mathbf{V}$ and a set of edges $\mathbf{E}$, such that each edge in $\mathbf{E}$ is a connection between a pair of vertices in $\mathbf{V}$.

greedy algorithm¶

An algorithm that makes locally optimal choices at each step.

growth rate¶

to-term:: lower bound :label: type
to-term:: upper bound :label: type

In algorithm analysis, the rate at which the cost of the algorithm grows as the size of its input grows.

hash function¶

In a hash system, the function that converts a key value to a position in the hash table. The hope is that this position in the hash table contains the record that matches the key value.

hash system¶

The implementation for search based on hash lookup in a hash table. The key is processed by a hash function, which returns a position in a hash table, which hopefully is the correct position in which to find the record corresponding to the search key.

hash table¶

The data structure (usually an array) that stores data records for lookup using hashing.

hashing¶

A search method that uses a hash function to convert a key into a position within a hash table. In a properly implemented hash system, that position in the table will have high probability of containing the record that matches the key value. Sometimes, the hash function will return an position that does not store the desired key, due to a process called collision. In that case, the desired record is found through a process known as collision resolution.

head¶

The beginning of a list.

header guard¶

In C and C++, used to prevent definitions copied into a file using the #include directive from being defined more than once.

#ifndef FOO_H_INCLUDED // any name uniquely mapped to file name
#define FOO_H_INCLUDED
// contents of the file are here
#endif

header node¶

Commonly used in implementations for a linked list or related structure, this node precedes the first element of the list. Its purpose is to simplify the code implementation by reducing the number of special cases that must be programmed for.

heap¶

This term has two different meanings. Sometimes, it is a synonym for free store.

A heap may also refer to a particular data structure. This data structure is a complete binary tree with the requirement that every node has a value greater than its children (called a max heap), or else the requirement that every node has a value less than its children (called a min heap). Since it is a complete binary tree, a heap is nearly always implemented using an array rather than an explicit tree structure. To add a new value to a heap, or to remove the extreme value (the max value in a max-heap or min value in a min-heap) and update the heap, takes $\Theta(\log n)$ time in the worst case. However, if given all of the values in an unordered array, the values can be re-arranged to form a heap in only $\Theta(n)$ time. Due to its space and time efficiency, the heap is a popular choice for implementing a priority queue.

height¶

The height of a tree is one more than the depth of the deepest node in the tree.

height balanced¶

The condition the depths of each subtree in a tree are roughly the same.

heuristic¶

A way to solve a problem that is not guarenteed to be optimal. While it might not be guarenteed to be optimal, it is generally expected (by the agent employing the heuristic) to provide a reasonably efficient solution.

heuristic algorithm¶

A type of approximation algorithm, that uses a heuristic to find a good, but not necessarily cheapest, solution to an optimization problem.

high-level language¶

A programming language that is designed to be easy for humans to read and write.

home position¶

In hashing, a synonym for home slot.

home slot¶

In hashing, this is the slot in the hash table determined for a given key by the hash function.

Huffman codes¶

The codes given to a collection of letters (or other symbols) through the process of Huffman coding. Huffman coding uses a Huffman coding tree to generate the codes. The codes can be of variable length, such that the letters which are expected to appear most frequently are shorter. Huffman coding is optimal whenever the true frequencies are known, and the frequency of a letter is independent of the context of that letter in the message.

Huffman coding tree¶

A Huffman coding tree is a full binary tree that is used to represent letters (or other symbols) efficiently. Each letter is associated with a node in the tree, and is then given a Huffman code based on the position of the associated node. A Huffman coding tree is an example of a binary trie.

Huffman tree¶

Shorter form of the term Huffman coding tree.

identifier¶

An identifier is used to name a type introduced into a program by a declaration.

An identifier is an arbitrarily long sequence of digits, underscores, lowercase and uppercase Latin letters. A valid identifier must begin with a non-digit character (Latin letter, underscore, Identifiers are case-sensitive (lowercase and uppercase letters are distinct), and every character is significant.

image-space decomposition¶

A from of key-space decomposition where the key space splitting points is predetermined (typically by splitting in half). For example, a Huffman coding tree splits the letters being coded into those with codes that start with 0 on the left side, and those with codes that start with 1 on the right side. This regular decomposition of the key space is the basis for a trie data structure. An image-space decomposition is in opposition to an object-space decomposition.

indexing¶

The process of associating a search key with the location of a corresponding data record. The two defining points to the concept of an index is the association of a key with a record, and the fact that the index does not actually store the record itself but rather it stores a reference to the record.

In this way, a collection of records can be supported by multiple indices, typically a separate index for each key field in the record.

induction step¶

Part of a proof by induction. In its simplest form, this is a proof of the implication that if the theorem holds for $n-1$, then it holds for $n$. As an alternative, see strong induction.

inherit¶

In object-oriented programming, the process by which a subclass gains data members and methods from a base class.

inorder traversal¶

In a binary tree, a traversal that first recursively visits the left child, then visits the root, an then recursively visits the right child.

instance variable¶

In object-oriented programming, a synonym for data member.

integrated development environment¶

IDE¶

A software suite that consolidates many tools developers need to write and test software. An IDE normally consists of a source code editor, version control, build automation tools, and a debugger. Most also automatically complete partially typed keywords and create commonly used code from templates.

interface¶

An interface is a class-like structure that only contains method signatures and fields. An interface does not contain an implementation of the methods or any data members.

intermediate code¶

A step in a typical compiler is to transform the original high-level language into a form on which it is easier to do other stages of the process. For example, some compilers will transform the original high-level source code into assembly code on which it can do code optimization, before translating it into its final executable form.

intermediate code generation¶

to-term:: Parse tree :label: walks through
to-term:: intermediate code :label: produces

A phase in a compiler, that walks through a parse tree to produce simple assembly code.

internal fragmentation¶

A condition that occurs when more than $N$ bytes are allocated to service a memory request for $N$ bytes, wasting free storage. This is often done to simplify memory management.

internal node¶

In a tree, any node that has at least one non-empty child is an internal node.

internal sort¶

A sorting algorithm that is applied to data stored in memory. This is in contrast to an external sort that is meant to work on data stored on disk.

interpreter¶

In contrast to a compiler that translates a high-level program into something that can be repeatedly executed to perform a computation, an interpreter directly performs computation on the high-level langauge.

This tends to make the computation much slower than if it were performed on the directly executable version produced by a compiler.

irreflexive¶

In set notation, binary relation $R$ on set $S$ is irreflexive if $aRa$ is never in the relation for any $a \in \mathbf{S}$.

iterable¶

A container in which each element can be visited using an iterator.

iterator¶

In a container such as a std::vector or std::set, a separate class that indicates position within the container, with support for traversing through all elements in the container.

kd tree¶

to-term:: discriminator :label: uses

A spatial data structure that uses a binary tree to store a collection of data records based on their (point) location in space. It uses the concept of a discriminator at each level to decide which single component of the multi-dimensional search key to branch on at that level. It uses a key-space decomposition, meaning that all data records in the left subtree of a node have a value on the corresponding discriminator that is less than that of the node, while all data records in the right subtree have a greater value.

key¶

to-term:: key space :label: has

A field or part of a larger record used to represent that record for the purpose of searching or comparing.

key sort¶

to-term:: key :label: uses

Any sorting operation applied to a collection of key-value pairs where the value in this case is a reference to a complete record (that is, a pointer to the record in memory or a position for a record on disk). This is in contrast to a sorting operation that works directly on a collection of records. The intention is that the collection of key-value pairs is far smaller than the collection of records themselves. As such, this might allow for an internal sort when sorting the records directly would require an external sort. The collection of key-value pairs can also act as an index.

key space¶

The range of values that a key value may take on.

key-space decomposition¶

to-term:: object-space decomposition :label: type
to-term:: image-space decomposition :label: type

The idea that the range for a search key will be split into pieces. There are two general approaches to this: object-space decomposition and image-space decomposition.

key-value pair¶

A standard solution for solving the problem of how to relate a key value to a record (or how to find the key for a given record) within the context of a particular index. The idea is to simply store as records in the index pairs of keys and records. Specifically, the index will typically store a copy of the key along with a reference to the record. The other standard solution to this problem is to pass a comparator function to the index.

language¶

A set of strings with specific meanings.

leaf node¶

In a binary tree, leaf node is any node that has two empty children. (Note that a binary tree is defined so that every node has two children, and that is why the leaf node has to have two empty children, rather than no children.) In a general tree, any node is a leaf node if it has no children.

level¶

In a tree, all nodes of depth $d$ are at level $d$ in the tree. The root is the only node at level 0, and its depth is 0.

lexical analysis¶

to-term:: interpreter :label: is

A phase of a compiler or interpreter responsible for reading in characters of the program or language and grouping them into tokens.

lexical scoping¶

Within programming languages, the convention of allowing access to a variable only within the block of code in which the variable is defined. A synonym for static scoping.

lifetime¶

For a variable, lifetime is the amount of time it will exist before it is destroyed.

LIFO¶

Abbreviation for “Last-In, First-Out”. This is the access paradigm for a stack, and an old terminolgy for the stack is “LIFO list”.

linear growth rate¶

For input size $n$, a growth rate of $cn$ (for $c$ any positive constant). In other words, the cost of the associated function is linear on the input size.

linear order¶

Another term for total order.

linear probing¶

In hashing, this is the simplest collision resolution method. Term $i$ of the probe sequence is simply $i$, meaning that collision resolution works by moving sequentially through the hash table from the home slot. While simple, it is also inefficient, since it quickly leads to certain free slots in the hash table having higher probability of being selected during insertion or search.

linear probing by steps¶

In hashing, this collision resolution method is a variation on simple linear probing. Some constant $c$ is defined such that term $i$ of the probe sequence is $ci$. This means that collision resolution works by moving sequentially through the hash table from the home slot in steps of size $c$. While not much improvement on linear probing, it forms the basis of another collision resolution method called double hashing, where each key uses a value for $c$ defined by a second hash function.

link error¶

After compiling, a link error occurs when each compilation unit compiles correctly, but in the next stage, the linker is unable to combine all the object code into a single valid executable file. Compare to compile-time error, runtime error, and semantic error.

linked list¶

An implementation for the list ADT that uses dynamic memory allocation of link nodes to store the list elements. Common variants are the singly linked list and doubly linked list.

list¶

A finite, ordered sequence of data items known as elements. This is close to the mathematical concept of a sequence. Note that “ordered” in this definition means that the list elements have position. It does not refer to the relationship between key values for the list elements (that is, “ordered” does not mean “sorted”).

literal¶

In a boolean expression, a literal is a boolean variable or its negation.

In the context of compilers, it is any constant value. Similar to a terminal.

load factor¶

In a hash table, the number of items contained in the table divided by the table size.

local variable¶

A variable declared within a function or method. It exists only from the time when the function is called to when the function exits. When a function is suspended (due to calling another function), the function’s local variables are stored in an activation record on the runtime stack.

logical form¶

The definition for a data type in terms of an ADT. Contrast to the physical form for the data type.

low-level language¶

A programming language that is designed to be easy for a computer to execute; also called machine language or assembly language.

lower bound¶

In algorithm analysis, a growth rate that is always less than or equal to the growth rate of the algorithm in question. In practice, this is the fastest-growing function that we know grows no faster than all but a constant number of inputs. It could be a gross under-estimate of the truth. Since the lower bound for the algorithm can be very different for different situations (such as the best case or worst case), we typically have to specify which situation we are referring to.

lower bounds proof¶

to-term:: adversary argument :label: example
to-term:: sorting lower bound :label: example
to-term:: search lower bound :label: example

A proof regarding the lower bound, with this term most typically referring to the lower bound for any possible algorithm to solve a given problem. Many problems have a simple lower bound based on the concept that the minimum amount of processing is related to looking at all of the problem’s input. However, some problems have a higher lower bound than that. For example, the lower bound for the problem of sorting ($\Omega(n \log n)$) is greater than the input size to sorting ($n$). Proving such “non-trivial” lower bounds for problems is notoriously difficult.

lvalue¶

An expression that identifies a non-temporary object.

lvalue reference¶

An alias or synonymn for an existing object. Often just referred to as a reference.

map¶

A data structure that relates a key to a record.

mapping¶

A function that maps every element of a given set to a unique element of another set; a correspondence.

max heap¶

A heap where every node has a key value greater than its children. As a consequence, the node with maximum key value is at the root.

member¶

In set notation, this is a synonym for element. In abstract design, a data item is a member of a type. In an object-oriented language, data members are data fields in an object.

member function¶

Each operation associated with the ADT is implemented by a member function or method.

memory leak¶

In programming, the act of creating garbage. In languages such as C and C++ that do not support garbage collection, repeated memory leaks will evenually cause the program to terminate.

method¶

In the object-oriented programming paradigm, a method is an operation on a class. A synonym for member function.

min heap¶

A heap where every node has a key value less than its children. As a consequence, the node with minimum key value is at the root.

mod¶

Abbreviation for the modulus function.

modulus¶

The modulus function returns the remainder of an integer division. Sometimes written $n \bmod m$ in mathematical expressions, the syntax in many programming languages is n % m.

multi-dimensional search key¶

A search key containing multiple parts, that works in conjunction with a multi-dimensional search structure. Most typically, a spatial search key representing a position in multi-dimensional (2 or 3 dimensions) space. But a multi-dimensional key could be used to organize data within non-spatial dimensions, such as temperature and time.

multi-dimensional search structure¶

to-term:: multi-dimensional search key :label: uses

A data structure used to support efficient search on a multi-dimensional search key. The main concept here is that a multi-dimensional search structure works more efficiently by considering the multiple parts of the search key as a whole, rather than making independent searches on each one-dimensional component of the key. A primary example is a spatial data structure that can efficiently represent and search for records in multi-dimensional space.

multilist¶

A list that may contain sublists. This term is sometimes used as a synonym to the term bag.

name¶

See identifier.

natural language¶

Any one of the languages that people speak that evolved naturally.

natural order¶

An ordering of a sequence of objects that seems ‘natural’ to most people. The ‘natural order’ of whole numbers is the sequence used to count things: 1,2,3,4,5,6… The natural order for words is sorted alphabetically.

neighbor¶

to-term:: adjacent :label: is
to-term:: graph :label: context

In a graph, a node $w$ is said to be a neighbor of node $v$ if there is an edge from $v$ to $w$.

node¶

The objects that make up a linked structure such as a linked list or binary tree. Typically, nodes are allocated using dynamic memory allocation.

non-strict partial order¶

In set notation, a relation that is reflexive, antisymmetric, and transitive.

non-terminal¶

In contrast to a terminal, a non-terminal is an abstract state in a production rule. Begining with the start symbol, all non-terminals must be converted into terminals in order to complete a derivation.

object¶

An instance of a class, that is, something that is created and takes up storage during the execution of a computer program. In the object-oriented programming paradigm, objects are the basic units of operation. Objects have state in the form of data members, and they know how to perform certain actions (functions).

object code¶

The output of the compiler after it translates the program.

object-oriented programming¶

object-oriented programming paradigm¶

An approach to problem-solving where all computations are carried out using objects.

object-space decomposition¶

A from of key-space decomposition where the key space is determined by the actual values of keys that are found. For example, a binary search tree stores a key value in its root, and all other values in the tree with lesser value are in the left subtree. Thus, the root value has split (or decomposed) the key space for that key based on its value into left and right parts. An object-space decomposition is in opposition to an image-space decomposition.

octree¶

The three-dimensional equivalent of the quadtree would be a tree with $2^3$ or eight branches.

Omega notation¶

In algorithm analysis, $\Omega$ notation is used to describe a lower bound. Roughly (but not completely) analogous to big-Oh notation used to define an upper bound.

open addressing¶

A synonym for closed hashing.

open hashing¶

open hash system¶

A hash system where multiple records might be associated with the same slot of a hash table. Typically this is done using a linked list to store the records. This is in contrast to a closed hash system.

operating system¶

The control program for a computer. Its purpose is to control hardware, manage resources, and present a standard interface to these to other software components.

optimization problem¶

Any problem where there are a (typically large) collection of potential solutions, and the goal is to find the best solution. An example is the Traveling Salesman Problem, where visiting $n$ cities in some order has a cost, and the goal is to visit in the cheapest order.

overflow¶

The condition where the amount of data stored in an entity has exceeded its capacity. For example, a node in a array can store a certain number of records. If a record is attempted to be inserted into a node that is full, then something has to be done to handle this case.

overflow bucket¶

In bucket hashing, this is the bucket into which a record is placed if the bucket containing the record’s home slot is full. The overflow bucket is logically considered to have infinite capacity, though in practice search and insert will become relatively expensive if many records are stored in the overflow bucket.

parameter¶

parameters¶

The values making up an input to a function.

parent¶

In a tree, the node $P$ that directly links to a node $A$ is the parent of $A$. $A$ is the child of $P$.

parent pointer representation¶

For trees, a node implementation where each node stores only a pointer to its parent, rather than to its children. This makes it easy to go up the tree toward the root, but not down the tree toward the leaves.

parity¶

The concept of matching even-ness or odd-ness, the basic idea behind using a parity bit for error detection.

parity bit¶

A common method for checking if transmission of a sequence of bits has been performed correctly. The idea is to count the number of 1 bits in the sequence, and set the parity bit to 1 if this number is odd, and 0 if it is even. Then, the transmitted sequence of bits can be checked to see if its parity matches the value of the parity bit. This will catch certain types of errors, in particular if the value for a single bit has been reversed. This was used, for example, in early versions of ASCII character coding.

parse¶

To examine a program and analyze the syntactic structure.

parse tree¶

A tree that represents the syntactic structure of an input string, making it easy to compare against a grammar to see if it is syntactically correct.

parser¶

to-term:: compiler :label: part of
to-term:: parse tree :label: build

A part of a compiler that takes as input the program text (or more typically, the tokens from the scanner), and verifies that the program is syntactically correct. Typically it will build a parse tree as part of the process.

partial order¶

In set notation, a binary relation is called a partial order if it is antisymmetric and transitive. If the relation is also reflexive, then it is a non-strict partial order. Alternatively, if the relation is also irreflexive, then it is a strict partial order.

partially ordered set¶

The set on which a partial order is defined is called a partially ordered set.

partition¶

The process of splitting a set into two parts, typically centering around a predicate expression or a value.

In quick sort, the central value is called the pivot value. One partition will contain values less then the pivot, while the other partition will contain values greater than the pivot value.

pass by reference¶

A reference to the variable is passed to the called function. So, any modifications will affect the original variable.

pass by value¶

A copy of a variable is passed to the called function. So, any modifications will not affect the original variable.

path¶

to-term:: tree :label: In
to-term:: vertex :label: sequence of

In tree or graph terminology, a sequence of vertices $v_1, v_2, ..., v_n$ forms a path of length $n-1$ if there exist edges from $v_i$ to $v_{i+1}$ for $1 \leq i < n$.

permutation¶

A permutation of a sequence $\mathbf{S}$ is the elements of $\mathbf{S}$ arranged in some order.

physical form¶

The implementation of a data type as a data structure. Contrast to the logical form for the data type.

Pigeonhole Principle¶

A commonly used lemma in Mathematics. A typical variant states: When $n+1$ objects are stored in $n$ locations, at least one of the locations must store two or more of the objects.

POD¶

An abbreviation for ‘plain old data’. Used to indicate a data structure containing no member functions and only publicly accessible data.

pointer¶

A variable whose value is the address of another variable; a link.

pointer-based implementation for binary tree nodes¶

A common way to implement binary tree nodes. Each node stores a data value (or a reference to a data value), and pointers to the left and right children. If either or both of the children does not exist, then a null pointer is stored.

polymorphism¶

Polymorphism¶

An object-oriented programming term meaning one name, many forms. It describes the ability of software to change its behavior dynamically. Two basic forms exist: runtime polymorphism and compile-time polymorphism.

pop¶

A specialized term used to indicate removing an element from a stack.

portability¶

A property of a program that can run on more than one kind of computer.

poset¶

An abbreviation for a partially ordered set.

position¶

The defining property of the list ADT, this is the concept that list elements are in a position. Many list ADTs support access by position.

postorder traversal¶

In a binary tree, a traversal that first recursively visits the left child, then recursively visits the right child, and then visits the root.

powerset¶

For a set $\mathbf{S}$, the power set is the set of all possible subsets for $\mathbf{S}$.

PR quadtree¶

A type of quadtree that stores point data in two dimensions. The root of the PR quadtree represents some square region of 2d space. If that space stores more than one data point, then the region is decomposed into four equal subquadrants, each represented recursively by a subtree of the PR quadtree. Since many leaf nodes of the PR quadtree will contain no data points, implementation often makes use of the flyweight design pattern. Related to the bintree.

predicate¶

predicate function¶

A function that returns a boolean value.

preorder traversal¶

In a binary tree, a traversal that first visits the root, then recursively visits the left child, then recursively visits the right child.

primary clustering¶

In hashing, the tendency in certain collision resolution methods to create clustering in sections of the hash table. The classic example is linear probing. This tends to happen when a group of keys follow the same :term`probe sequence` during collision resolution.

primitive element¶

In set notation, this is a single element that is a member of the base type for the set. This is as opposed to an element of the set being another set.

primitive type¶

A data type whose values contain no subparts. An example is the integers. A synonym for simple type and code block.

priority¶

A quantity assigned to each of a collection of tasks that indicate importance for order of processing. For example, in an operating system, there could be a collection of processes (jobs) ready to run. The operating system must select the next task to execute, based on their priorities.

priority queue¶

An ADT whose primary operations of insert of records, and deletion of the greatest (or, in an alternative implementation, the least) valued record. Most often implemented using the heap data structure. The name comes from a common application where the records being stored represent tasks, with the ordering values based on the priorities of the tasks.

probe function¶

In hashing, the function used by a collision resolution method to calculate where to look next in the hash table.

probe sequence¶

In hashing, the series of slots visited by the probe function during collision resolution.

problem¶

A task to be performed. It is best thought of as a function or a mapping of inputs to outputs.

problem instance¶

A specific selection of values for the parameters to a problem. In other words, a specific set of inputs to a problem. A given problem instance has a size under some cost model.

problem solving¶

The process of formulating a problem, finding a solution, and expressing the solution.

procedural¶

Typically referring to the procedural programming paradigm, in contrast to the object-oriented programming paradigm.

procedural programming paradigm¶

Procedural programming uses a list of instructions (and procedure calls) that define a series of computational steps to be carried out. This is in contrast to the object-oriented programming paradigm.

production¶

production rule¶

A grammar is comprised of production rules. The production rules consist of terminals and non-terminals, with one of the non-terminals being the start symbol. Each production rule replaces one or more non-terminals (perhaps with associated terminals) with one or more terminals and non-terminals. Depending on the restrictions placed on the form of the rules, there are classes of languages that can be represented by specific types of grammars. A derivation is a series of productions that results in a string (that is, all non-terminals), and this derivation can be represented as a parse tree.

program¶

An instance, or concrete representation, of an algorithm in some programming language. A sequence of instructions that specifies to a computer actions and computations to be performed. A program can refer to the compiled system object code, or to the original source code.

programming language¶

A formal notation for representing solutions.

proof¶

to-term:: lower bounds proof :label: example
to-term:: NP-Completeness proof :label: example
to-term:: proof by contradiction :label: type
to-term:: proof by induction :label: type

The establishment of the truth of anything, a demonstration.

proof by contradiction¶

A mathematical proof technique that proves a theorem by first assuming that the theorem is false, and then uses a chain of reasoning to reach a logical contradiction. Since when the theorem is false a logical contradiction arises, the conclusion is that the theorem must be true.

proof by induction¶

A mathematical proof technique similar to recursion. It is used to prove a parameterized theorem $S(n)$, that is, a theorem where there is a induction variable involved (such as the sum of the numbers from 1 to $n$). One first proves that the theorem holds true for a base case, then one proves the implication that whenever $S(n)$ is true then $S(n+1)$ is also true. Another variation is strong induction.

pseudo-random probing¶

In hashing, this is a collision resolution method that stores a random permutation of the values 1 through the size of the hash table. Term $i$ of the probe sequence is simply the value of position $i$ in the permuation.

push¶

A specialized term used to indicate inserting an element onto a stack.

push_back¶

A specialized term used to indicate appending an element onto a vector.

quadratic growth rate¶

A growth rate function of the form $cn^2$ where $n$ is the input size and $c$ is a constant.

quadratic probing¶

In hashing, this is a collision resolution method that computes term $i$ of the probe sequence using some quadratic equation $ai^2 _ bi + c$ for suitable constants $a, b, c$. The simplest form is simply to use $i^2$ as term $i$ of the probe sequence.

quadtree¶

A full tree where each internal node has four children. Most typically used to store two dimensional spatial data. Related to the bintree. The difference is that the quadtree splits all dimensions simultaneously, while the bintree splits one dimension at each level. Thus, to extend the quadtree concept to more dimensions requires a rapid increase in the number of splits (for example, 8 in three dimensions).

queue¶

A list-like structure in which elements are inserted only at one end, and removed only from the other one end.

radix¶

Synonym for base. The number of digits in a number representation. For example, we typically represent numbers in base (or radix) 10. Hexidecimal is base (or radix) 16.

RAII¶

Resource Acquisition Is Initialization is the C++ term for a programming style in which critical resources are tied to the object which owns them. Because they are typically allocated in class constructors and destroyed in class destructors, in other languages, this is sometimes called Constructor Acquires, Destructor Releases

range¶

The set of possible outputs for a function.

record¶

A collection of information, typically implemented as an object in an object-oriented programming language. Many data structures are organized containers for a collection of records.

recurrence relation¶

A recurrence relation (or less formally, recurrence) defines a function by means of an expression that includes one or more (smaller) instances of itself. A classic example is the recursive definition for the factorial function, $F(n) = n*F(n-1)$.

recursion¶

The process of using recursive calls. An algorithm is recursive if it calls itself to do part of its work. See recurrence relation.

recursive call¶

Within a recursive function, it is a call that the function makes to itself.

recursive data structure¶

A data structure that is partially composed of smaller or simpler instances of the same data structure. For example, linked lists and binary trees can be viewed as recursive data structures.

recursive function¶

A function that includes a recursive call.

reference¶

A value that enables a program to directly access some particular data item. An example might be a byte position within a file where the record is stored, or a pointer to a record in memory. (Note that Java makes a distinction between a reference and the concept of a pointer, since it does not define a reference to necessarily be a byte position in memory.)

reference count algorithm¶

An algorithm for garbage collection. Whenever a reference is made from a variable to some memory location, a counter associated with that memory location is incremented. Whenever the reference is changed or deleted, the reference count is decremented. If this count goes to zero, then the memory is considered free for reuse. This approach can fail if there is a cycle in the chain of references.

reflexive¶

In set notation, binary relation $R$ on set $S$ is reflexive if $aRa$ for all $a \in \mathbf{S}$.

regular type¶

A user defined type that behaves like a ‘regular’ built-in (fundamental) type. Regular types support the following operations:

Operation	Definition
Default constructor	T a;
Copy constructor	T a = b;
Destructor	~T (a);
Assignment	a = b;
Equality	a == b;
Inequality	a != b;
Ordering	a < b;

relation¶

In set notation, a relation $R$ over set $\mathbf{S}$ is a set of ordered pairs from $\mathbf{S}$.

root¶

In a tree, the topmost node of the tree. All other nodes in the tree are descendants of the root.

runtime environment¶

The environment in which a program (of a particular programming language) executes. The runtime environment handles such activities as managing the runtime stack, the free store, and the garbage collector, and it conducts the execution of the program.

runtime error¶

An error that does not occur until the program has started to execute but that prevents the program from continuing. Compare to compile-time error, link error, and semantic error.

runtime polymorphism¶

Runtime polymorphism¶

A form of polymorphism known as Overriding. Overridden methods are those which implement a new method with the same signature as a method inherited from its base class. Compare to compile-time polymorphism.

runtime stack¶

The place where an activation record is stored when a subroutine is called during a program’s runtime.

rvalue¶

An expression that identifies a temporary object or a value not associated with any object, such as a literal.

rvalue reference¶

Sometimes called a forwarding reference. A reference that is allowed to refer to an rvalue. That is, a temporary object or an rvalue not associated with any object.

scanner¶

to-term:: compiler :label: part of
to-term:: lexical analysis :label: responsible for

The part of a compiler that is responsible for doing lexical analysis.

scope¶

A region of the program where a defined variable, definition, or function exists. Beyond that point the variable can not be accessed.

search key¶

A field or part of a record that is used to represent the record when searching. For example, in a database of customer records, we might want to search by name. In this case the name field is used as the search key.

search lower bound¶

The problem of searching in an array has provable lower bounds for specific variations of the problem. For an unsorted array, it is $\Omega(n)$ comparisons in the worst case, typically proved using an adversary argument. For a sorted array, it is $\Omega(\log n)$ in the worst case, typically proved using an argument similar to the sorting lower bound proof. However, it is possible to search a sorted array in the average case in $O(\log \log n)$ time.

search problem¶

Given a particular key value $K$, the search problem is to locate a record $(k_j, I_j)$ in some collection of records L such that $k_j = K$ (if one exists). Searching is a systematic method for locating the record (or records) with key value $k_j = K$.

search tree¶

to-term:: Binary Search Tree :label: example
to-term:: search trie :label: example

A tree data structure that makes search by key value more efficient. A type of container, it is common to implement an index using a search tree. A good search tree implementation will guarantee that insertion, deletion, and search operations are all $\Theta(\log n)$.

search trie¶

to-term:: alphabet trie :label: example
to-term:: binary trie :label: example

Any search tree that is a trie.

searching¶

Given a search key $K$ and some collection of records L, searching is a systematic method for locating the record (or records) in L with key value $k_j = K$.

secondary clustering¶

In hashing, the tendency in certain collision resolution methods to create clustering in sections of the hash table. In primary clustering, this is caused by a cluster of keys that don’t necessarily hash to the same slot but which following significant portions of the same probe sequence during collision resolution. Secondary clustering results from the keys hashing to the same slot of the table (and so a collision resolution method that is not affected by the key value must use the same probe sequence for all such keys). This problem can be resolved by double hashing since its probe sequence is determined in part by a second hash function.

semantic error¶

An error in a program or expression that makes it do something other than what the programmer intended. Compare to compile-time error, link error, and runtime error.

semantics¶

The meaning of a program or piece of text.

separate chaining¶

In hashing, a synonym for open hashing

sequence¶

In set notation, a collection of elements with an order, and which may contain duplicate-valued elements. A sequence is also sometimes called a tuple or a vector.

sequence container¶

A container in which elements can be accessed sequentially. The underlying data may be a contiguous block of memory, as with vector and array, or may be non-contiguous memory, as with list.

sequential tree representation¶

A representation that stores a series of node values with the minimum information needed to reconstruct the tree structure. This is a technique for serializing a tree.

serialization¶

The process of taking a data structure in memory and representing it as a sequence of bytes. This is sometimes done in order to transmit the data structure across a network or store the data structure in a stream, such as on disk. Deserialization reconstructs the original data structure from the serialized representation.

set¶

A collection of distinguishable members or elements.

set former¶

A way to define the membership of a set, by using a text description. Example: $\{x\ |\ x\ \mbox{is a positive integer}\}$.

set product¶

Written $\mathbf{Q} \times \mathbf{P}$, the set product is a set of ordered pairs such that ordered pair $(a, b)$ is in the product whenever $a \in \mathbf{P}$ and $b \in \mathbf{Q}$. For example, when $\mathbf{P} = \{2, 3, 5\}$ and $\mathbf{Q} = \{5, 10\}$, $\mathbf{Q} \times \mathbf{P} = \{(2, 5),\ (2, 10),\ (3, 5),\ (3, 10),\ (5, 5),\ (5, 10)\}$.

shallow copy¶

Copying a reference or pointer value without copying the actual content.

sibling¶

In a tree, a sibling of node $A$ is any other node with the same parent as $A$.

signature¶

In a programming language, the signature for a function is its return type and its list of parameters and their types.

simple type¶

A data type whose values contain no subparts. An example is the integers. A synonym for primitive type and :term”fundamental type.

simulating recursion¶

If a programming language does not support recursion, or if you want to implement the effects of recursion more efficiently, you can use a stack to maintain the collection of subproblems that would be waiting for completion during the recursive process. Using a loop, whenever a recursive call would have been made, simply add the necessary program state to the stack. When a return would have been made from the recursive call, pop the previous program state off of the stack.

singly linked list¶

A linked list implementation variant where each list node contains access an pointer only to the next element in the list.

slot¶

In hashing, a position in a hash table.

software engineering¶

The study and application of engineering to the design, development, and maintenance of software.

software reuse¶

In software engineering, the concept of reusing a piece of software. In particular, using an existing piece of software (such as a function or library) when creating new software.

sorting lower bound¶

The lower bound for the problem of sorting is $\Omega(n \log n)$. This is traditionally proved using a decision tree model for sorting algorithms, and recognizing that the minimum depth of the decision tree for any sorting algorithm is $\Omega(n \log n)$ since there are $n!$ permutations of the $n$ input records to distinguish between during the sorting process.

sorting problem¶

Given a set of records $r_1$, $r_2$, …, $r_n$ with key values $k_1$, $k_2$, …, $k_n$, the sorting problem is to arrange the records into any order $s$ such that records $r_{s_1}$, $r_{s_2}$, …, $r_{s_n}$ have keys obeying the property $k_{s_1} \leq k_{s_2} \leq ... \leq k_{s_n}$. In other words, the sorting problem is to arrange a set of records so that the values of their key fields are in non-decreasing order.

source code¶

A program, stored in a file, in a high-level language before being compiled or interpreted.

spatial¶

Referring to a position in space.

spatial application¶

An application what has spatial aspects. In particular, an application that stores records that need to be searched by location.

spatial attribute¶

An attribute of a record that has a position in space, such as the coordinate. This is typically in two or more dimensions.

spatial data¶

Any object or record that has a position (in space).

spatial data structure¶

to-term:: bintree :label: example
to-term:: kd tree :label: example
to-term:: PR quadtree :label: example

A data structure designed to support efficient processing when a spatial attribute is used as the key. In particular, a data structure that supports efficient search by location, or finds all records within a given region in two or more dimensions. Examples of spatial data structures to store point data include the bintree, the PR quadtree and the kd tree.

stack¶

A list-like structure in which elements may be inserted or removed from only one end.

start symbol¶

In a grammar, the designated non-terminal that is the initial point for deriving a string in the language.

static scoping¶

A synonym for lexical scoping.

strategy¶

An approach to accomplish a task, often encapsulated as an algorithm. Also the name for a design pattern that separates the algorithm for performing a task from the control for applying that task to each member of a collection. A good example is a generic sorting function that takes a collection of records (such as an array) and a “strategy” in the form of an algorithm that knows how to extract the key from a record in the array. Only subtly different from the visitor design pattern, where the difference is primarily one of intent rather than syntax. The strategy design pattern is focused on encapsulating an activity that is part of a larger process, so that different ways of performing that activity can be substituted. The visitor design pattern is focused on encapsulating an activity that will be performed on all members of a collection so that completely different activities can be substituted within a generic method that accesses all of the collection members.

stream¶

The process of delivering content in a serialized form.

strict partial order¶

In set notation, a relation that is irreflexive, antisymmetric, and transitive.

strong induction¶

An alternative formulation for the induction step in a proof by induction. The induction step for strong induction is: If Thrm holds for all $k, c \leq k < n$, then Thrm holds for $n$.

subclass¶

In object-oriented programming, any class within a class hierarchy that inherits from some other class. A synonym for derived class.

subset¶

In set theory, a set $A$ is a subset of a set $B$, or equivalently $B$ is a superset of $A$, if all elements of $A$ are also elements of $B$.

subtree¶

A subtree is a subset of the nodes of a binary tree that includes some node $R$ of the tree as the subtree root along with all the descendants of $R$.

summation¶

The sum of costs for some function applied to a range of parameter values. Often written using Sigma notation. For example, the sum of the integers from 1 to $n$ can be written as $\sum_{i=1}^{n} i$.

superset¶

In set theory, a set $A$ is a subset of a set $B$, or equivalently $B$ is a superset of $A$, if all elements of $A$ are also elements of $B$.

symbol table¶

As part of a compiler, the symbol table stores all of the identifiers in the program, along with any necessary information needed about the identifier to allow the compiler to do its job.

symmetric¶

In set notation, relation $R$ is symmetric if whenever $aRb$, then $bRa$, for all $a, b \in \mathbf{S}$.

symmetric matrix¶

A square matrix that is equal to its transpose. Equivalently, for a $n \times n$ matrix $A$, for all $i,j < n$, $A[i, j] = A[j, i]$.

syntax¶

The set of rules that defines the valid symbol combinations that define valid statements or expressions in a specific language.

syntax analysis¶

to-term:: parse tree :label: generates
to-term:: tokens :label: accepts

A phase of compilation that accepts tokens, checks if program is syntactically correct, and then generates a parse tree.

syntax error¶

An error in a program that makes it impossible to parse — and therefore impossible to interpret.

tail¶

The end of a list.

template¶

A template is a specific way in C++ to write generic functions and classes.

A template by itself is not a class, type, function, or any other entity. It defines a recipe for generating a class or function.

terminal¶

A specific character or string that appears in a production rule. In contrast to a non-terminal, which represents an abstract state in the production. Similar to a literal, but this is the term more typically used in the context of a compiler.

test-driven development¶

Test-driven development (TDD) is a software development process that relies on the repetition of a very short development cycle: requirements are turned into very specific test cases, then the software is improved to pass the new tests, only. This is opposed to software development that allows software to be added that is not proven to meet requirements.

Kent Beck, who is credited with having developed the technique, stated in 2003 that TDD encourages simple designs and inspires confidence.

token¶

One of the basic elements of the syntactic structure of a program, analogous to a word in a natural language.

total order¶

A binary relation on a set where every pair of distinct elements in the set are comparable (that is, one can determine which of the pair is greater than the other).

trailing return type¶

A C++11 language feature that allows a function or lambda expression to defer evaluating the function return type. Example:

template<class T>
auto mul(T a, T b) -> decltype(a*b){
  return a*b;
}

[](double x, double y) -> int {return x*y;}

transitive¶

In set notation, relation $R$ is transitive if whenever $aRb$ and $bRc$, then $aRc$, for all $a, b, c \in \mathbf{S}$.

transpose¶

In the context of linear algebra, the transpose of a matrix $A$ is another matrix $A^T$ created by writing the rows of $A$ as the columns of $A^T$.

traversal¶

traverse¶

Any process for visiting all of the objects in a collection (such as a tree or list) in some order.

tree¶

A tree $\mathbf{T}$ is a finite set of one or more nodes such that there is one designated node $R$, called the root of $\mathbf{T}$. If the set $(\mathbf{T} -\{R\})$ is not empty, these nodes are partitioned into $n > 0$ disjoint sets $\mathbf{T}_0$, $\mathbf{T}_1$, …, $\mathbf{T}_{n-1}$, each of which is a tree, and whose roots $R_1, R_2, ..., R_n$, respectively, are children of $R$.

tree traversal¶

A traversal performed on a tree. Traditional tree traversals include preorder and postorder traversals for both binary and general trees, and :term`inorder traversal` for binary search trees.

trie¶

to-term:: alphabet trie :label: example
to-term:: binary trie :label: example
to-term:: search trie :label: example

A form of search tree where an internal node represents a split in the key space at a predetermined location, rather than split based on the actual key values seen. For example, a simple binary search trie for key values in the range 0 to 1023 would store all records with key values less than 512 on the left side of the tree, and all records with key values equal to or greater than 512 on the right side of the tree. A trie is always a full tree. Folklore has it that the term comes from “retrieval”, and should be pronounced as “try” (in contrast to “tree”, to distinguish the differences in the space decomposition method of a search tree versus a search trie). The term “trie” is also sometimes used as a synonym for the alphabet trie.

truth table¶

In symbolic logic, a table that contains as rows all possible combinations of the boolean variables, with a column that shows the outcome (true or false) for the expression when given that row’s truth assignment for the boolean variables.

tuple¶

In set notation, another term for a sequence.

In C++, the class tuple.

two’s complement¶

A mathematical operation on binary numbers, as well as a binary signed number representation based on this operation.

type¶

A collection of values.

unary function¶

A function that accepts one parameter.

unit test¶

A software test method in which a single unit of source code, for example, a single function is tested in isolation. Unit tests are short code fragments, typically created by programmers as part of the development process. In a process like test-driven development the unit tests are written before any other code.

unsorted list¶

A list where the records stored in the list can appear in any order (as opposed to a sorted list). An unsorted list can support efficient ($\Theta(1)$) insertion time (since you can put the record anywhere convenient), but requires $\Theta(n)$ time for both search and deletion.

unvisited¶

In graph algorithms, this refers to a node that has not been processed at the current point in the algorithm.

upper bound¶

In algorithm analysis, a growth rate that is always greater than or equal to the growth rate of the algorithm in question. In practice, this is the slowest-growing function that we know grows at least as fast as all but a constant number of inputs. It could be a gross over-estimate of the truth. Since the upper bound for the algorithm can be very different for different situations (such as the best case or worst case), we typically have to specify which situation we are referring to.

variable-length coding¶

Given a collection of objects, a variable-length coding scheme assigns a code to each object in the collection using codes that can be of different lengths. Typically this is done in a way such that the objects that are most likely to be used have the shortest codes, with the goal of minimizing the total space needed to represent a sequence of objects, such as when representing the characters in a document. This is in contrast to fixed-length coding.

vector¶

In set notation, another term for a sequence. As a data structure, the term vector usually used as a synonym for a dynamic array.

vertex¶

Another name for a node in a graph.

visit¶

During the process of a traversal on a list or tree the action that takes place on each node.

visitor¶

A design pattern where a traversal process is given a function (known as the visitor) that is applied to every object in the collection being traversed. For example, a generic tree or graph traversal might be designed such that it takes a function parameter, where that function is applied to each node.

volatile¶

In the context of computer memory, this refers to a memory that loses all stored information when the power is turned off.

worst case¶

In algorithm analysis, the problem instance from among all problem instances for a given input size $n$ that has the greatest cost. Note that the worst case is not when $n$ is big, since we are referring to the worst from a class of inputs (i.e, we want the worst of those inputs of size $n$).

You have attempted of activities on this page