Term

Definition
a tree in which the heights of subtrees are approximately equal. 


Term

Definition
a selfbalancing sorted binary tree, in which the heights of subtrees differ by at most 1. 


Term

Definition
a selfbalancing 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 (onetoone 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 recomputing 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 highestpriority (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, onetoone. 


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 highestpriority 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 multipledimensioned 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 selfbalancing 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 objectoriented 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 problemsolving strategy in which a problem is broken down into subproblems, until simple subproblems 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
firstin, firstout; 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
lastin, firstout; 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 treestructured form by enclosing its tags. 

