Algorithms and Data Structures Glossary (Starting with "E")

Free glossaries at TanslationDirectory.com

Algorithms and Data Structures Glossary
(Starting with "E")

By www.nist.gov,
Gaithersburg, Maryland, U.S.A.

paul . black [at] nist . gov
http://www.nist.gov/dads

Become a member of TranslationDirectory.com at just $12 per month (paid per year)

Advertisements:

Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

E

easy split, hard merge
edge
edge coloring
edge connectivity
edge crossing
edge-weighted graph: see weighted graph
edit distance: see Levenshtein distance
edit operation
edit script
efficiency
8 queens
elastic-bucket trie
element uniqueness
end-of-string
enfilade
ERCW: see exclusive read, concurrent write
EREW: see exclusive read, exclusive write
Euclidean algorithm: see Euclid's algorithm
Euclidean distance
Euclidean Steiner tree
Euclidean traveling salesman problem
Euclid's algorithm
Euler cycle
Eulerian graph
Eulerian path: see Euler cycle
exact string matching: see string matching
EXCELL
exchange sort: see bubble sort
exclusive or: see xor
exclusive read, concurrent write
exclusive read, exclusive write
exhaustive search
existential state
expandable hashing
expander graph
exponential
extended binary tree
extended Euclid's algorithm
extended k-d tree
extendible hashing
external chaining: see separate chaining
external index
external memory algorithm
external memory data structure
external merge
external node: see leaf
external quicksort
external radix sort
external sort
extrapolation search: see interpolation search
extremal
extreme point

easy split, hard merge

(algorithmic technique)

Definition: A recursive algorithm, especially a sort algorithm, where dividing (splitting) into smaller problems is quick or simple and combining (merging) the solutions is time consuming or complex.

Generalization (I am a kind of ...)
divide and conquer.

Aggregate parent (I am a part of or used in ...)
merge sort, strand sort, insertion sort.

Note: Although the notion is wide spread, I first heard this term from Doug Edwards about 1994.

Called "Divide form" of using divide and conquer in [ATCH99, page 3-3].

Author: PEB

edge

(definition)

Definition: A connection between two vertices of a graph. In a weighted graph, each edge has an number, called a "weight." In a directed graph, an edge goes from one vertex, the source, to another, the target, and hence makes connection in only one direction.

Also known as arc.

Aggregate parent (I am a part of or used in ...)
directed graph, undirected graph, weighted graph.

Note: That is, in a directed graph, an edge goes from the source to the target.

Author: PEB

edge coloring

(definition)

Definition: An assignment of colors (or any distinct marks) to the edges of a graph. A coloring is a proper coloring if no two adjacent edges have the same color.

Note: From Algorithms and Theory of Computation Handbook, page 7-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Authors: PEB,CRC-A

edge connectivity

(definition)

Definition: (1) The smallest number of edges whose deletion will cause a connected graph to not be connected. (2) For a pair of vertices s and t in a graph, the smallest number of edges whose deletion will separate s from t.

Author: GS

edge crossing

(definition)

Definition: Two different edges cross in a graph drawing if their geometric representations intersect. The number of crossings in a graph drawing is the number of pairs of edges which cross.

Note: From Algorithms and Theory of Computation Handbook, page 9-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

edit operation

(definition)

Definition: On a string, the operation of deletion, insertion, or substitution performed on a single symbol. On a tree, the deletion of a node v followed by the reassignment of all children of v to the node of which v was formerly a child, the insertion of a new node followed by the reassignment of some arcs departing from the parent of the new node, or the substitution of the label of one of the nodes with another label. Each edit operation may have an associated nonnegative real number representing its cost.

Note: From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

edit script

(definition)

Definition: A sequence of viable edit operations on a string or tree.

Author: CRC-A

efficiency

(definition)

Definition: The resources an algorithm used to find an answer. It is usually measured in terms of the theoretical computations, such as comparisons or data moves, the memory used, the number of messages passed, the number of disk accesses, etc.

Author: PEB

8 queens

(classic problem)

Definition: Place eight chess queens on an 8 × 8 board such that no queen can attack another. Efficiently find all possible placements.

Generalization (I am a kind of ...)
n queens.

Author: PEB

elastic-bucket trie

(data structure)

Definition: A variant of a bucket trie in which each leaf node for n strings is a bucket allocated to hold exactly n strings.

Generalization (I am a kind of ...)
bucket trie.

Note: The name comes from reTRIEval and is pronounced, "tree." See the historical note at trie.

Author: PEB

More information

Thomas Papadakis, Skip Lists and Probabilistic Analysis of Algorithms, PhD Thesis, Faculty of Mathematics, University of Waterloo, Canada, May 1993, page 106.

element uniqueness

(classic problem)

Definition: The problem of determining if there are duplicates in a set of numbers.

Note: From Algorithms and Theory of Computation Handbook, page 1-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

end-of-string

(definition)

Definition: A special character indicating the end of a string.

Author: PEB

Euclidean distance

(definition)

Definition: The straight line distance between two points. In a plane with p₁ at (x₁, y₁) and p₂ at (x₂, y₂), it is √((x₁ - x₂)² + (y₁ - y₂)²).

Note: In N dimensions, the Euclidean distance between two points p and q is √(∑_i=1^N (p_i-q_i)²) where p_i (or q_i) is the coordinate of p (or q) in dimension i.

Author: PEB

Euclidean Steiner tree

(definition)

Definition: A tree of minimum Euclidean distance connecting a set of points, called terminals, in the plane. This tree may include points other than the terminals, which are called Steiner points.

Author: JLG

Euclidean traveling salesman problem

(classic problem)

Definition: Find a path of minimum Euclidean distance between points in a plane which includes each point exactly once and returns to its starting point.

Note: This can be generalized to higher dimensions, for instance, points in a 3-dimensional space. This problem is a special case of traveling salesman since the cost between points is the planar distance instead of arbitrary weights.

Author: PEB

Euclid's algorithm

(algorithm)

Definition: An algorithm to compute the greatest common divisor of two positive integers. It is Euclid(a,b){if (b=0) then return a; else return Euclid(b, a mod b);}. The run time complexity is O((log a)(log b)) bit operations.

Also known as Euclidean algorithm.

Note: After [CLR90, page 810].

Author: PEB

Euler cycle

(definition)

Definition: A path through a graph which starts and ends at the same vertex and includes every edge exactly once.

Also known as Eulerian path, Königsberg bridges problem.

Aggregate parent (I am a part of or used in ...)
Christofides algorithm.

Note: "Euler" is pronounced "oil-er." A Hamiltonian cycle includes each vertex once; an Euler cycle includes each edge once.

Author: PEB

More information

examples and explanations

Historical Note
Euler defined the cycle to solve the puzzle of finding a path across every bridge of the German city of Königsberg exactly once.

Eulerian graph

(definition)

Definition: A graph that has an Euler cycle.

Note: From Algorithms and Theory of Computation Handbook, page 6-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

EXCELL

(data structure)

Definition: A point access method using a dynamic multidimensional array.

Note: After [GG98].

Author: PEB

exclusive read, concurrent write

(definition)

Definition: A parallel memory model in which only one processor can read from any one memory location at one time, but multiple processors can write simultaneously to a single memory location.

Also known as ERCW.

Author: PMS

exclusive read, exclusive write

(definition)

Definition: A parallel memory model in which only one processor can read from any one memory location at one time, and only one processor can write to any one memory location at one time.

Also known as EREW.

Author: PMS

exhaustive search

(algorithmic technique)

Definition: An algorithm that finds a solution by trying every possibility.

Author: BB

More information

All the Needles in a Haystack: Can Exhaustive Search Overcome Combinatorial Chaos?

existential state

(definition)

Definition: A state in a nondeterministic Turing machine from which the machine accepts if any move leads to acceptance.

Note: From Algorithms and Theory of Computation Handbook, page 24-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

exponential

(definition)

Definition: (1) Any function which is the sum of constants times other constants to the power of the argument: f(x)=Σ_i=0^k c_ib_i^xp_i. (2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by an exponential function of the problem size, n. More formally if there exists k > 1 such that m(n) = Θ(kⁿ) and there exists c such that m(n) = O(cⁿ).

Author: PEB

extended binary tree

(data structure)

Definition: A binary tree with special nodes replacing every null subtree. Every regular node has two children, and every special node has no children.

Note: After [Knuth97, 1:399, Sect. 2.3.4.5].

Author: PEB

extended Euclid's algorithm

(algorithm)

Definition: An algorithm to find the greatest common divisor, g, of two positive integers, a and b, and coefficients, h and j, such that g = ha + jb.

Note: These coefficients are useful for computing modular multiplicative inverses. After [CLR90, page 811].

Author: PEB

extended k-d tree

(data structure)

Definition: A spatial access method where successive levels are split along different dimensions into nonoverlapping cells. Objects are indexed in all cells they intersect.

Note: After [GG98].

Author: PEB

extendible hashing

(data structure)

Definition: A hash table in which the hash function is the last few bits of the key and the table refers to buckets. Table entries with the same final bits may use the same bucket. If a bucket overflows, it splits, and if only one entry referred to it, the table doubles in size. If a bucket is emptied by deletion, entries using it are changed to refer to an adjoining bucket, and the table may be halved.

Generalization (I am a kind of ...)
dynamic hashing.

Note: The table may be seen as a flattened complete binary tree where the buckets are (possibly) shared leaf nodes.

Author: PEB

More information

Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, and H. Raymond Strong, Extendible Hashing - A Fast Access Method for Dynamic Files, ACM Transactions on Database Systems, 4(3):315-344, 1979.

external index

(data structure)

Definition: An auxiliary data structure added to a main data structure to improve operations, such as a search on a secondary key.

Note: The implementation probably embeds parts of the external index in the primary data structure, such as adding a few fields to each node. If items are added to or deleted from the primary data structure, the external index must be maintained, too. Data may have multiple external indexes, such as a data base of movies with inverted indexes for title, actors, and genre.

Author: PEB

external memory algorithm

(algorithm)

Definition: An algorithm that is efficient when accessing most of the data is very slow, such as, on disk.

Note: See [Vitt01]. The external memory could be magnetic tape or even main memory if the cache is very fast.

Author: PEB

external memory data structure

(data structure)

Definition: A data structure that is efficient even when accessing most of the data is very slow, such as, on a disk.

Note: See [Vitt01]. The external memory could be magnetic tape or even main memory if the cache is very fast.

Author: PEB

external merge

(algorithm)

Definition: To combine multiple sorted data streams into a single sorted stream using external storage.

Author: ASK

external quicksort

(algorithm)

Definition: Read the M/2 first and last elements into a buffer (the buffer acts like the pivot in quicksort), and sort them. Read the next element from the beginning or end to balance writing. If the next element is less than the least of the buffer, write it to available space at the beginning. If greater than the greatest, write it to the end. Otherwise write the greatest or least of the buffer, and put the next element in the buffer. Keep the maximum lower and minimum upper keys written to avoid resorting middle elements that are in order. When done, write the buffer. Recursively sort the smaller partition, and loop to sort the remaining partition.

Generalization (I am a kind of ...)
external sort, in-place sort.

Aggregate child (... is a part of or used in me.)
partition, divide and conquer, recursion.

Note: Performance is terrible if the external memory does not have random (direct) access.

Author: PEB

external sort

(definition)

Definition: Any sort algorithm that uses external memory, such as tape or disk, during the sort. Since most common sort algorithms assume high-speed random access to all intermediate memory, they are unsuitable if the values to be sorted don't fit in main memory.

Specialization (... is a kind of me.)
balanced multiway merge, cascade merge sort, optimal polyphase merge sort, oscillating merge sort, polyphase merge sort, external radix sort, external quicksort.

Note: Algorithms may read the initial values from magnetic tape or write sorted values to disk, but this is not using external memory during the sort. Note that even though virtual memory may mask the use of disk, sorting sets of data much larger than main memory may be much faster using an explicit external sort.

See [Knuth98, vol. 3, Sect. 5.4] for an extensive treatment.

Author: PEB

More information

Geeta Chaudhry's PhD thesis which includes new external sort algorithms and comparisons with other external sort algorithms.

extremal

(definition)

Definition: Some of the entries of the auxiliary array used in a string matching algorithm. An entry is d-extremal if it is the deepest entry on its diagonal to be given value d.

Author: CRC-A

extreme point

(definition)

Definition: A corner point of a polyhedron. More formally, a point which cannot be expressed as a convex combination of other points in the polyhedron.

Note: From Algorithms and Theory of Computation Handbook, pages 19-26 and 32-39, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z