| Definition |
Term |
| a description of operations on a data type that could have multiple possible implementations. | |
| describes a graph with no cycles (circular paths). | |
| a representation of a graph in which each node has a list of nodes that are adjacent to it, i.e. connected to it by an arc. | |
| a representation of a graph in which a boolean matrix contains a 1 at position (i,j) iff there is an arc from node i to node j. | |
| in a tree, the union of a node's parent and the parent's ancestors. | |
| a link between two nodes in a graph. | |
| A contiguous block of memory containing elements of the same type, accessed by numeric index. | |
| a list of pairs, where each pair has a key and a value associated with the key. | |
| a self-balancing sorted binary tree, in which the heights of subtrees differ by at most 1. | |
| a tree with a high branching factor, to minimize the number of disk accesses required to access a desired record. | |
| in a tree search, to move back from the node currently being examined to its parent. | |
| a tree in which the heights of subtrees are approximately equal. | |
| a simple case that can be solved easily, without recursion. | |
| an abstracted function that describes the amount of computer time or memory space required by an algorithm, as a function of problem size. For problems larger than a certain size, | |
| describes a relation that is both injective and surjective (one-to-one and onto). | |
| a data structure that implements a complete binary tree within an array, such that every parent node has a value that is less than the value of either of its children. | |
| search of a binary tree or other structure, in which the size of the set to be searched is cut in half at each step. | |
| a tree in which each node has at most two children. | |
| an association of a name with a value. | |
| a list structure that represents a set of bindings. | |
| a matrix whose elements are 0 or 1. | |
| a number that is defined as an object, so that it has a runtime type and methods that can be used, e.g. Integer in Java. | |
| in a search tree, the number of children of a given node. Often, the branching factors of individual nodes will vary, so an average value may be used. | |
| a collection, such as a linked list, of values that hash to the same value. | |
| to save a value locally to save re-computing or transferring it in the future. | |
| a set of pairs (x, y) of elements from two sets X and Y. | |
| in a tree, a node pointed to by a parent node. | |
| a queue implemented within an array, where the first element of the array logically follows the last element. | |
| a linked list in which the last element points back to the first element. | |
| in object-oriented programming, a description of a set of similar objects. | |
| a situation in which many elements has to the same hash value. | |
| when two values to be stored in a hash table have the same hash value. | |
| the act of comparing two values to determine which is greater according to some ordering. | |
| 1. in Lisp, the function that constructs a pair of pointers, or basic element of list structure. 2. to make a cons data structure. 3. a cons data structure. | |
| describes a function that makes a new data structure but does not modify its arguments. | |
| a circular path in a graph. | |
| directed acyclic graph. | |
| the number of links between the root of a tree and the leaves. | |
| a search in which children of a node are considered (recursively) before siblings are considered. | |
| to convert from a pointer (address) to the data that is pointed to. | |
| all nodes below a given node in a tree. | |
| a pattern that describes a set of similar programs. | |
| describes a function that modifies its arguments. | |
| depth-first search. | |
| an optimal greedy algorithm to find the minimum distance and shortest path in a weighted graph from a give start node. | |
| describes an arc that can only be traversed in one direction, or a graph with such arcs. | |
| a directed graph with no cycles. Every tree is a DAG, but a DAG may be more general. | |
| a simulation in terms of events, in which the highest-priority (least time) event is removed from an event queue and executed, which may have the effect of scheduling future events | |
| a problem-solving strategy in which a problem is broken down into sub-problems, until simple subproblems are reached. | |
| the set of values that are the source values of a mapping. | |
| a linked list in which each element has both forward and backward pointers. | |
| a link or arc between nodes in a graph. | |
|
| Definition |
Term |
| a binary Boolean function whose output is 1 if its inputs are different. Abbreviated XOR. | |
| another term for hashing with buckets. | |
| a sort using external storage in addition to main memory. | |
| describes a process in which every arriving customer will eventually be served. | |
| first-in, first-out | |
| a process that removes unwanted elements from a collection. | |
| a way of implementing trees that uses two pointers per node but can represent an arbitrary number of children of a node. | |
| to process a set of items using a specified function; another term for reduce. | |
| storage that is no longer pointed to by any variable and therefore can no longer be accessed. | |
| the process of collecting garbage for recycling. | |
| describes a thought experiment or view of an entity. | |
| a series in which each successive term is multiplied by a constant less than 1, e.g. 1 + 1/2 + 1/4 + 1/8 + ... | |
| an item (or description of items) being sought in a search. | |
| a formal description of a language in terms of vocabulary and rules for writing phrases and sentences. | |
| a set of nodes and arcs connecting the nodes. | |
| an algorithm that always tries the solution path that appears to be the best. | |
| a function that is deterministic but randomizing, i.e. whose output is a relatively small integer that appears to be a random function of the key value. | |
| describes a data structure that cannot be changed once it has been created, such as Integer or String in Java. | |
| describes a sort that does not require any additional memory. | |
| describes a mapping in which each element of the domain maps to a single element of the range. Also, one-to-one. | |
| an order of processing a tree in which the parent node is processed in between its children. | |
| a node of a tree that has children. | |
| a sort using only the main memory of the computer. | |
| given two sets, the intersection is the set of elements that are members of both sets. | |
| a problem that is so hard (typically exponential) that it cannot be solved unless the problem is small. | |
| an object containing data and methods to iterate through a collection of data, allowing processing of one data item at a time. | |
| a tree node containing a contents value but with no children. | |
| last-in, first out | |
| O(n), a problem whose solution requires a linear amount of time or space if the problem is of size n. | |
| a pointer to the next element in a linked list. | |
| a sequence of records, where each record contains a link to the next one. | |
| in a hash table, the fraction of the table's capacity that is filled. | |
| in MapReduce, a program that processes an element of the input and emits one or more (key, value) pairs. | |
| association of one or more elements of a Range set with each element of a Domain set. | |
| a program that controls a set of other programs or devices. | |
| a priority queue in which the maximum element is removed first. | |
| the processing of data in such a way that data that are located near each other are processed nearby in time. | |
| to combine two ordered linear structures into one. | |
| a priority queue in which the minimum element is removed first. | |
| an element of a linked list, tree, or graph, often represented by a data structure. | |
| a runtime error that occurs when an operation such as a method call is attempted on a null pointer. | |
| a data structure that can be identified at runtime as being a member of a class. | |
| describes a sorting algorithm that can process items one at a time. | |
| describes a mapping in which each element of the domain maps to a single element of the range. Also, injective. | |
| describes a mapping in which each element of the range is the target of some element of the domain. Also, surjective. | |
| a description of the kinds of objects that exist in a computer program, e.g. a Java class hierarchy. | |
| in a search tree, a program that changes a state into a child state, e.g. a move in a game. | |
| in a tree, a node that points to a given node. | |
| analysis of a sentence of a language to determine the elements of the sentence and their relationship and meaning. | |
| a sequence of steps along arcs in a graph. | |
| a representation of a class of objects, containing some constant elements in relation to variable elements. | |
| a part of a pattern that can match variable parts of an input. | |
|
| Definition |
Term |
| in Quicksort, a 'center' value used in partitioning the set to be sorted. | |
| a variable containing the address of other data. | |
| an order of processing a tree in which the parent node is processed after its children. | |
| an order of processing a tree in which the parent node is processed before its children. | |
| a queue in which the highest-priority elements are removed first; with a priority value, the earliest arrival is removed first. | |
| O(n2), a problem whose solution requires a quadratic amount of time or space if the problem is of size n. | |
| a data structure representing a sequence of items, which are removed in the same order as they were inserted. | |
| describes a data structure or device in which all accesses have the same cost, O(1). | |
| an algorithm in which the data to be processed or the deice to process it is randomly selected. | |
| a set of values that are the targets of a mapping. | |
| a case where a program calls itself. | |
| a condition of the input data where the data will be handled by call(s) to the same program. | |
| a self-balancing binary tree in which nodes are 'colored' red or black. The longest path from the root to a leaf is no more than twice the length of the shortest path. | |
| to apply a given function to the elements of a given list. Also, fold. | |
| a pointer to data. | |
| a type in which variables of that type are pointers to objects. | |
| to apply a different hashing function to a key when a collision occurs. | |
| the top node of a tree, from which all other nodes can be reached. | |
| a stack containing a stack frame of variable values for each active invocation of a procedure. | |
| the ability of an algorithm or hardware system to grow to handle a larger number of inputs. | |
| to look through a data structure until a goal object is found. | |
| an extra record at the start or end of a data structure such as a linked list, to simplify the processing. | |
| given two sets, the set difference is the set of elements of the first set that are not members of the second set. | |
| to hide similar items with the same name. | |
| the shortest path between a start node and a goal node in a weighted graph. < | |
| any effect of a procedure other than returning a value, e.g. printing or modifying a data structure. | |
| a path between two nodes in a graph that does not revisit any intermediate node. | |
| a program or device that operates under control of a master. | |
| to modify the order of a set of elements so that a desired ordering holds between them, e.g. alphabetic order. | |
| an array in which most of the elements are zero or missing. | |
| a graph in which any node is connected to relatively few other nodes. | |
| a self-balancing binary tree that places recently accessed elements near the top of the tree for fast access. | |
| describes a sort algorithm in which the relative position of elements with equal keys is unchanged after sorting. | |
| a section of the runtime stack holding the values of all variables for one invocation of a procedure. | |
| the amount of space on the runtime stack required for execution of a program. | |
| a description of the state of a process, such as a board game. | |
| a case where two data structures share some elements. | |
| the next element in a linked list. | |
| describes a mapping in which each element of the range is the target of some element of the domain. Also, onto. | |
| a data structure that links names to information about the objects denoted by the names. | |
| a function whose value either does not involve a recursive call, or is exactly the value of a recursive call. | |
| a classification of objects into a tree structure that groups related objects. | |
| changing the links in a binary tree to change the relative heights of the child subtrees, while leaving the sort order of the tree unchanged. | |
| describes a graph in which the arcs may be followed in either direction. | |
| given two sets, the union is the set of elements that are members of either set. | |
| converting an abstract syntax tree into a sentence in a language, such as a programming language. | |
| a node in a graph. | |
| a number that denotes the cost of following an arc in a graph. | |
| an ordering that can be guaranteed to terminate, e.g. starting at a positive integer and counting down to 0. | |
| Extensible Markup Language, a way of writing data in a tree-structured form by enclosing it in tags. | |
| exclusive or. | |
|
