Shared Flashcard Set

Details

Vocab Set #4
Words for final
30
Computer Science
12/08/2010

Term
 A*
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
 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
 balanced tree
Definition
 a tree in which the heights of subtrees are approximately equal.
Term
 bijective
Definition
 describes a relation that is both injective and surjective (one-to-one and onto)
Term
 binding list
Definition
 a list structure that represents a set of bindings
Term
 cache
Definition
 to save a value locally to save re-computing or transferring it in the future
Term
 collision
Definition
 when two values to be stored in a hash table have the same hash value
Term
 cycle
Definition
 a circular path in a graph
Term
 Dijkstra's algorithm
Definition
 an optimal greedy algorithm to find the minimum distance and shortest path in a weighted graph from a given start node
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
 exclusive or
Definition
 Definitiona binary Boolean function whose output is 1 if its inputs are different. Abbreviated XOR.
Term
 fold
Definition
 to process a set of items using a specified function; another term for reduce
Term
 greedy algorithm
Definition
 an algorithm that always tries the solution path that appears to be the best
Term
 in-place
Definition
 describes a sort that does not require any additional memory
Term
 iterator
Definition
 an object containing data and methods to iterate through a collection of data, allowing processing of one data item at a time.
Term
 map
Definition
 in MapReduce, a program that processes an element of the input and emits one or more (key, value) pairs
Term
 max queue
Definition
 a priority queue in which the maximum element is removed first
Term
 min queue
Definition
 a priority queue in which the minimum element is removed first
Term
 one-to-one
Definition
 describes a mapping in which each element of the domain maps to a single element of the range. Also, injective
Term
 path
Definition
 a sequence of steps along arcs in a graph
Term
 pivot
Definition
 in Quicksort, a "center" value used in partitioning the set to be sorted
Term
 range
Definition
 a set of values that are the targets of a mapping
Term
 rehash
Definition
 to apply a different hashing function to a key when a collision occurs
Term
 row-major order
Definition
 a way of storing a multiple-dimensioned array in memory, such that elements of a row are in adjacent memory addresses
Term
 simple path
Definition
 a path between two nodes in a graph that does not revisit any intermediate node
Term
 sparse array
Definition
 an array in which most of the elements are either 0 or empty
Term
 Splay tree
Definition
 a self-balancing binary tree that places recently accessed elements near the top of the tree for fast access.
Term
 symbol table
Definition
 a data structure that links names to information about the objects denoted by the names.
Term
 tree rotation
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
 vertex
Definition
 a node in a graph
Supporting users have an ad free experience!