# Shared Flashcard Set

## Details

Data Structures Part 3
Vocab List for CS 315 at the University of Texas
20
Computer Science
05/17/2011

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
 depth
Definition
 the number of links between the root of a tree and the leaves.
Term
 depth-first search
Definition
 a search in which children of a node are considered (recursively) before siblings are considered.
Term
 dereference
Definition
 to convert from a pointer (address) to the data that is pointed to.
Term
 descendants
Definition
 all nodes below a given node in a tree.
Term
 design pattern
Definition
 a pattern that describes a set of similar programs.
Term
 destructive
Definition
 describes a function that modifies its arguments.
Term
 DFS
Definition
 depth-first search.
Term
 Dijkstra's algorithm
Definition
 an optimal greedy algorithm to find the minimum distance and shortest path in a weighted graph from a give start node.
Term
 directed
Definition
 describes an arc that can only be traversed in one direction, or a graph with such arcs.
Term
 directed acyclic graph
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
 divide and conquer
Definition
 a problem-solving strategy in which a problem is broken down into sub-problems, until simple subproblems are reached.
Term
 domain
Definition
 the set of values that are the source values of a mapping.
Term
Definition
 a linked list in which each element has both forward and backward pointers.
Term
 edge
Definition
 a link or arc between nodes in a graph.
Term
 exclusive or
Definition
 a binary Boolean function whose output is 1 if its inputs are different. Abbreviated XOR
Term
 extendible hashing
Definition
 another term for hashing with buckets.
Term
 external sort
Definition
 a sort using external storage in addition to main memory.
Term
 fair
Definition
 describes a process in which every arriving customer will eventually be served.
Supporting users have an ad free experience!