# Shared Flashcard Set

## Details

Vocab Set #6
Words for final
29
Computer Science
12/08/2010

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
 AVL tree
Definition
 a self-balancing sorted binary tree, in which the heights of subtrees differ by at most 1.
Term
 B-tree
Definition
 a tree with a high branching factor, to minimize the number of disk accesses required to access a desired record
Term
 binding
Definition
 an association of a name with a value
Term
 bucket
Definition
 a collection, such as a linked list, of values that hash to the same value
Term
 clustering
Definition
 a situation in which many elements hash to the same hash value
Term
 critical path
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
 dense graph
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
 directed acyclic graph
Definition
 a directed graph with no cycles. Every tree is a DAG, but a DAG may be more general.
Term
 edge
Definition
 a link or arc between nodes in a graph
Term
 external sort
Definition
 a sort using external storage in addition to main memory
Term
 graph
Definition
 a set of nodes and arcs connecting the nodes
Term
 heuristic
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
 internal sort
Definition
 a sort using only the main memory of the computer
Term
Definition
 in a hash table, the fraction of the table's capacity that is filled
Term
 master
Definition
 a program that controls a set of other programs or devices
Term
 memory locality
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
 on-line
Definition
 describes a sorting algorithm that can process items one at a time
Term
 parsing
Definition
 analysis of a sentence of a language to determine the elements of the sentence and their relationship and meaning
Term
 pattern variable
Definition
 a part of a pattern that can match variable parts of an input
Term
 randomized algorithm
Definition
 an algorithm in which the data to be processed or the device to process it is randomly selected
Term
 reduce
Definition
 to apply a given function to the elements of a given list. Also, fold.
Term
 shortest path
Definition
 the shortest path between a start node and a goal node in a weighted graph
Term
 slave
Definition
 a program or device that operates under control of a master
Term
 spatial locality
Definition
 being close together in space, i.e. memory address.
Term
 surjective
Definition
 describes a mapping in which each element of the range is the target of some element of the domain. Also, onto.
Term
 topological sort
Definition
 a linear ordering of nodes of an acyclic graph, such that a node follows all of its graph predecessors in the ordering
Term
 unparsing
Definition
 converting an abstract syntax tree into a sentence in a language, such as a programming language
Term
 XOR
Definition
 exclusive or
Supporting users have an ad free experience!