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
| A self-balancing sorted binary tree, in which the heights of subtrees differ by at most 1. |
|
|
Term
|
Definition
| A tree in which the heights of subtrees are approximately equal |
|
|
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 has 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. sparsh graph. |
|
|
Term
|
Definition
| An optimal greedy algorithm to find the minimum distance and shortest path in a weighted graph from a give 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 1if 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 the input and emits one or more (key, value) pairs |
|
|
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 (e.g. RAM) is larger, and the slowest memory (e.g. 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 used in partition the set to be sorted |
|
|
Term
|
Definition
| A queue in which the highest-priority elements are removed first; with 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
| 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. |
|
|
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 multiply-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 a scheduling graph ,the amount of time by which the time of an activity could be increased without affecting the overall competition 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. |
|
|
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 programming language |
|
|
Term
|
Definition
|
|
Term
|
Definition
| A number that denotes the cost of following an arc ina graph |
|
|
Term
|
Definition
|
|
