Shared Flashcard Set

Details

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

Additional Computer Science Flashcards

 


 

Cards

Term
adjacency list
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
load factor
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!