Term
|
Definition
| a tree in which the heights of subtrees are approximately equal. |
|
|
Term
|
Definition
| a self-balancing sorted binary tree, in which the heights of subtrees differ by at most 1. |
|
|
Term
|
Definition
| a self-balancing binary tree in which the 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. |
|
|
Term
|
Definition
| a self=balancing binary tree that places recently accessed elements near the top of the tree for fast access. |
|
|
Term
|
Definition
| a heuristic search algorithm that attempts to find a desired goal using a heuristic function to estimate the distance from a given node to the goal. |
|
|
Term
|
Definition
| describes a graph with no cycles (circular paths) |
|
|
Term
|
Definition
| 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 |
|
|
Term
|
Definition
| 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. |
|
|
Term
|
Definition
| a link between two nodes in a graph |
|
|
Term
|
Definition
| information transfer rate of a network connection, in bits/second |
|
|
Term
|
Definition
| a tree with a high branching factor, to minimize the number of disk accesses required to access a desired record |
|
|
Term
|
Definition
| describes a relation that is both injective and surjective (one-to-one and onto) |
|
|
Term
|
Definition
| 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 |
|
|
Term
|
Definition
| an association of a name with a value |
|
|
Term
|
Definition
| a list structure that represents a set of bindings |
|
|
Term
|
Definition
| a matrix whose elements are 0 or 1 |
|
|
Term
|
Definition
| a collection, such as a linked list, of values that hash to the same value |
|
|
Term
|
Definition
| to save a value locally to save re-computing or transferring it in the future |
|
|
Term
|
Definition
| a set of pairs (x, y) of elements from two sets X and Y |
|
|
Term
|
Definition
| a situation in which many elements hash to the same hash value |
|
|
Term
|
Definition
| when two values to be stored in a hash table have the same hash value |
|
|
Term
|
Definition
| the act of comparing two values to determine which is greater according to some ordering |
|
|
Term
|
Definition
| in a PERT chart or scheduling graph, a path from the initial state to the goal such that any increase in time required along the critical path will increase the time to complete the whole project |
|
|
Term
|
Definition
| a circular path in a graph |
|
|
Term
|
Definition
|
|
Term
|
Definition
| a graph such that a large fraction of possible connections among nodes are present, i.e. the number of edges is of the order of the number of vertices squared. cf. sparse graph |
|
|
Term
|
Definition
| an optimal greedy algorithm to find the minimum distance and shortest path in a weighted graph from a given start node |
|
|
Term
|
Definition
| describes an arc that can only be traversed in one direction, or a graph with such arcs |
|
|
Term
|
Definition
| a directed graph with no cycles. Every tree is a DAG, but a DAG may be more general. |
|
|
Term
| discrete event simulation |
|
Definition
| 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 |
|
|
Term
|
Definition
| the set of values that are the source values of a mapping |
|
|
Term
|
Definition
| a link or arc between nodes in a graph |
|
|
Term
|
Definition
| a binary Boolean function whose output is 1 if its inputs are different. Abbreviated XOR. |
|
|
Term
|
Definition
| another term for hashing with buckets |
|
|
Term
|
Definition
| a sort using external storage in addition to main memory |
|
|
Term
|
Definition
| to process a set of items using a specified function; another term for reduce |
|
|
Term
|
Definition
| a series in which each successive term is multiplied by a constant less than 1, e.g. 1 + 1/2 + 1/4 + 1/8 .... |
|
|
Term
|
Definition
| a set of nodes and arcs connecting the nodes |
|
|
Term
|
Definition
| an algorithm that always tries the solution path that appears to be the best |
|
|
Term
|
Definition
| 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 |
|
|
Term
|
Definition
| a function that estimates the distance from a given node to the goal in A* search. More generally, a method that generally gives good advice about which direction to go or how to approach a problem |
|
|
Term
|
Definition
| describes a sort that does not require any additional memory |
|
|
Term
|
Definition
| describes a mapping in which each element of the domain maps to a single element of the range. Also, one-to-one. |
|
|
Term
|
Definition
| a sort using only the main memory of the computer |
|
|
Term
|
Definition
| an object containing data and methods to iterate through a collection of data, allowing processing of one data item at a time. |
|
|
Term
|
Definition
| the delay between asking for data from an I/O device and the beginning of data transfer |
|
|
Term
|
Definition
| in a hash table, the fraction of the table's capacity that is filled |
|
|
Term
|
Definition
| in MapReduce, a program that processes an element of a Range set with each element of a Domain set. |
|
|
Term
|
Definition
| association of one or more elements of a Range set with each element of a Domain set |
|
|
Term
|
Definition
| a program that controls a set of other programs or devices |
|
|
Term
|
Definition
| a priority queue in which the maximum element is removed first |
|
|
Term
|
Definition
| the use of several kinds of memory hardware in a computer system, where the fastest memory (e.g. cache) is smallest, slower memory (RAM) is larger, and the slowest memory (disk) is largest |
|
|
Term
|
Definition
| the processing of data in such a way that data that are located near each other by memory address are accessed nearby in time |
|
|
Term
|
Definition
| a priority queue in which the minimum element is removed first |
|
|
Term
|
Definition
| a tree formed from the nodes of a graph and a subset of its edges, such that all nodes are connected and the total cost of the edges is minimal |
|
|
Term
|
Definition
| describes a sorting algorithm that can process items one at a time |
|
|
Term
|
Definition
| describes a mapping in which each element of the domain maps to a single element of the range. Also, injective |
|
|
Term
|
Definition
| describes a mapping in which each element of the range is the target of some element of the domain. Also, surjective. |
|
|
Term
|
Definition
| analysis of a sentence of a language to determine the elements of the sentence and their relationship and meaning |
|
|
Term
|
Definition
| a sequence of steps along arcs in a graph |
|
|
Term
|
Definition
| a representation of a class of objects, containing some constant elements in relation to variable elements |
|
|
Term
|
Definition
| a part of a pattern that can match variable parts of an input |
|
|
Term
|
Definition
| in Quicksort, a "center" value using in partitioning the set to be sorted |
|
|
Term
|
Definition
| a queue in which the highest-priority elements are removed first; without a priority value, the earliest arrival is removed first |
|
|
Term
|
Definition
| an algorithm in which the data to be processed or the device to process it is randomly selected |
|
|
Term
|
Definition
| a set of values that are the targets of a mapping |
|
|
Term
|
Definition
| to apply a given function to the elements of a given list. Also, fold. |
|
|
Term
|
Definition
| to apply a different hashing function to a key when a collision occurs |
|
|
Term
|
Definition
| a way of storing a multiple-dimensioned array in memory, such that elements of a row are in adjacent memory addresses |
|
|
Term
|
Definition
| the ability of an algorithm or hardware system to grow to handle a larger number of inputs |
|
|
Term
|
Definition
| the shortest path between a start node and a goal node in a weighted graph |
|
|
Term
|
Definition
| a path between two nodes in a graph that does not revisit any intermediate node |
|
|
Term
|
Definition
| in a PERT chart or scheduling graph, the amount of time by which the time of an activity could be increased without affecting the overall completion time |
|
|
Term
|
Definition
| a program or device that operates under control of a master |
|
|
Term
|
Definition
| an array in which most of the elements are zero or missing |
|
|
Term
|
Definition
| a graph in which any node is connected to relatively few other nodes. cf. dense graph. |
|
|
Term
|
Definition
| being close together in space, i.e. memory address. |
|
|
Term
|
Definition
| a self-balancing binary tree that places recently accessed elements near the top of the tree for fast access. |
|
|
Term
|
Definition
| describes a sort algorithm in which the relative position of elements with equal keys is unchanged after sorting. |
|
|
Term
|
Definition
| describes a mapping in which each element of the range is the target of some element of the domain. Also, onto. |
|
|
Term
|
Definition
| a data structure that links names to information about the objects denoted by the names. |
|
|
Term
|
Definition
| being close together in time, i.e. memory accesses that occur within a short time of each other. |
|
|
Term
|
Definition
| a linear ordering of nodes of an acyclic graph, such that a node follows all of its graph predecessors in the ordering |
|
|
Term
|
Definition
| 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 |
|
|
Term
|
Definition
| describes a graph in which the arcs may be followed in either direction |
|
|
Term
|
Definition
| converting an abstract syntax tree into a sentence in a language, such as a programming language |
|
|
Term
|
Definition
|
|
Term
|
Definition
| a number that denotes the cost of following an arc in a graph |
|
|
Term
|
Definition
|
|
Term
|
Definition
| a description of operations on a data type that could have multiple possible implementations. |
|
|
Term
|
Definition
| in a tree, the union of a node's parent and the parent's ancestors. |
|
|
Term
|
Definition
| a contiguous block of memory containing elements of the same type, accessed by numeric index. |
|
|
Term
|
Definition
| a list of pairs, where each pair has a key and a value associated with that key. |
|
|
Term
|
Definition
| in a tree search, to move back from the node currently being examined to its parent. |
|
|
Term
|
Definition
| a simple case that can be solved easily, without recursion. |
|
|
Term
|
Definition
| 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, the actual time or space required will be less than the big O multiplied by some constant. |
|
|
Term
|
Definition
| a tree in which each node has at most two children. |
|
|
Term
|
Definition
| 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. |
|
|
Term
|
Definition
| 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. |
|
|
Term
|
Definition
| 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. |
|
|
Term
|
Definition
| in a tree, a node pointed to by a parent node. |
|
|
Term
|
Definition
| a linked list in which the last element points back to the first element. |
|
|
Term
|
Definition
| a queue implemented within an array, where the first element of the array logically follows the last element. |
|
|
Term
|
Definition
| in object-oriented programming, a description of a set of similar objects. |
|
|
Term
|
Definition
| 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. |
|
|
Term
|
Definition
| describes a function that makes a new data structure but does not modify its arguments. |
|
|
Term
|
Definition
| the number of links between the root of a tree and its leaves. |
|
|
Term
|
Definition
| a search in which children of a node are considered (recursively) before siblings are considered. |
|
|
Term
|
Definition
| to convert from a pointer(address) to the data that is pointed to. |
|
|
Term
|
Definition
| all nodes below a given node in a tree. |
|
|
Term
|
Definition
| a pattern that describes a set of similar programs. |
|
|
Term
|
Definition
| describes a function that modifies its arguments. |
|
|
Term
|
Definition
|
|
Term
|
Definition
| a problem-solving strategy in which a problem is broken down into sub-problems, until simple sub-problems are reached. |
|
|
Term
|
Definition
| a linked list in which each element has backward and forward pointers. |
|
|
Term
|
Definition
| describes a process in which every arriving customer will eventually be served. |
|
|
Term
|
Definition
| first-in, first-out; describes the ordering of a queue. |
|
|
Term
|
Definition
| a process that removes unwanted elements from a collection. |
|
|
Term
|
Definition
| a way of implementing trees that uses two pointers per node but can represent an arbitrary number of children of a node. |
|
|
Term
|
Definition
| storage that is no longer pointed to by any variable and therefore can no longer be accessed. |
|
|
Term
|
Definition
| the process of collecting garbage for recycling. |
|
|
Term
|
Definition
| describes a thought experiment or view of an entity. |
|
|
Term
|
Definition
| an item (or description of items) being sought in a search. |
|
|
Term
|
Definition
| a formal description of a language in terms of vocab and rules for writing phrases and sentences. |
|
|
Term
|
Definition
| describes a data structure that cannot be changed once it has been created, such as Integer or String in Java. |
|
|
Term
|
Definition
| an order of processing a tree in which the parent node is processed in between its children |
|
|
Term
|
Definition
| a node of a tree that has children |
|
|
Term
|
Definition
| given two sets, it's the set of elements that are members of both sets. |
|
|
Term
|
Definition
| a problem that is so hard(typically exponential) that it cannot be solved unless the problem is small. |
|
|
Term
|
Definition
| a tree node containing a contents value but with no children. |
|
|
Term
|
Definition
| last-in, first-out; describes the order of a stack. |
|
|
Term
|
Definition
| O(n), a problem whose solution requires a linear amount of time or space if the problem is size of n. |
|
|
Term
|
Definition
| a pointer to the next element in a linked list. |
|
|
Term
|
Definition
| a sequence of records, where each record contains a link to the next one. |
|
|
Term
|
Definition
| to combine two ordered linear structures into one. |
|
|
Term
|
Definition
| an element in a linked list, tree, or graph, often represented by a data structure. |
|
|
Term
|
Definition
| a runtime error that occurs when an operation such as a method call is attempted on a null pointer. |
|
|
Term
|
Definition
| a data structure that can be identified at runtime as being a member of a class |
|
|
Term
|
Definition
| a description of the kinds of objects that exist in a computer program, e.g. a Java class hierarchy. |
|
|
Term
|
Definition
| in a tree, a node that points to a given node. |
|
|
Term
|
Definition
| in a search tree, a program that changes a state into a child state, e.g. a move in a game. |
|
|
Term
|
Definition
| a variable containing the address of other data. |
|
|
Term
|
Definition
| an order of processing a tree in which the parent node is processed after its children. |
|
|
Term
|
Definition
| a way of processing a tree in which the parent node is processed before its children. |
|
|
Term
|
Definition
| O(n^2), a problem whose solution requires a quadratic amount of time or space if the problem is of size n. |
|
|
Term
|
Definition
| a data structure representing a sequence of items, which are removed in the same order as they were inserted. |
|
|
Term
|
Definition
| describes a data structure or device in which all accesses have the same cost, O(1) |
|
|
Term
|
Definition
| a case where a program calls itself. |
|
|
Term
|
Definition
| a condition of the input data where the data will be handled by call(s) to the same problem. |
|
|
Term
|
Definition
|
|
Term
|
Definition
| a type in which variables of that type are pointers to objects. |
|
|
Term
|
Definition
| the top node of a tree, from which all other nodes can be reached. |
|
|
Term
|
Definition
| a stack containing a stack frame of variable values for each active invocation of a procedure. |
|
|
Term
|
Definition
| the area of program text over which a variable can be referenced. |
|
|
Term
|
Definition
| to look through a data structure until a goal object is found. |
|
|
Term
|
Definition
| an extra record at the start or end of a data structure such as a linked list, to simplify processing. |
|
|
Term
|
Definition
| given two sets, the set difference is the set of elements of the first set that are not members of the second set. |
|
|
Term
|
Definition
| to hide similar items with the same name. |
|
|
Term
|
Definition
| any effect of a procedure other than returning a value, e.g. printing or modifying a data strucure. |
|
|
Term
|
Definition
| to modify the order of a set of elements so that a desired ordering holds between them, e.g. alphabetic order. |
|
|
Term
|
Definition
| a section of the runtime stack holding the values of all variables for one invocation of a procedure. |
|
|
Term
|
Definition
| the amount of space on the runtime stack required for execution. |
|
|
Term
|
Definition
| a description of the state of a process, such as a board game. |
|
|
Term
|
Definition
| a case where two data structures share some elements. |
|
|
Term
|
Definition
| the next element in a linked list. |
|
|
Term
|
Definition
| a function whose value either does not involve a recursive call, or is exactly the value of a recursive call. |
|
|
Term
|
Definition
| a classification of objects into a tree structure that groups related objects. |
|
|
Term
|
Definition
| given two sets, the union is the set of elements that are members of either set. |
|
|
Term
|
Definition
| an ordering that can be guaranteed to terminate, e.g. starting at a positive integer and counting down to 0. |
|
|
Term
|
Definition
| Extensible Markup Language, a way of writing data in a tree-structured form by enclosing its tags. |
|
|
