Shared Flashcard Set

Details

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

Additional Computer Science Flashcards

 


 

Cards

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
adjacency matrix
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
Definition
a 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!