Algorithms and Data Structures Glossary
(Starting with "L")
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
L
- labeled graph
- language
- last-in, first-out
- Las Vegas algorithm
- lattice
- layered graph
- LCM: see least common multiple
- LCS
- leaf
- least common multiple
- leftist tree
- left rotation
- Lempel-Ziv-Welch
- level-order traversal
- Levenshtein distance
- lexicographical order
- LIFO: see stack
- linear
- linear congruential generator
- linear hash
- linear hashing
- linear insertion sort: see insertion sort
- linear order: see total order
- linear probing
- linear probing sort
- linear product
- linear program
- linear quadtree
- linear search
- link
- linked list
- list
- list contraction
- little-o notation
- Lm distance
- load factor
- local alignment
- locality-sensitive hashing
- local optimum
- logarithmic
- longest common subsequence
- longest common substring
- Lotka's law
- lower bound
- lower triangular matrix
- lowest common ancestor
- l-reduction
- lucky sort
- LZW compression: see Lempel-Ziv-Welch
labeled graph
(definition)
Definition:
A graph which has labels associated with each edge or each vertex.
Note:
Adapted from [Wier98, page 466].
Author: PEB
language
(definition)
Definition:
A set of strings over some fixed alphabet. A characterization of inputs which may or may not be solved by algorithms.
Also known as formal language.
Note:
From Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
last-in, first-out
(definition)
Definition:
A policy that the most recently arrived item is processed first. A stack implements this.
Note:
A depth-first search checks newly encountered nodes last-in, first-out.
Author: PEB
Las Vegas algorithm
(algorithmic technique)
Definition:
A randomized algorithm that always produces correct results, with the only variation from one run to another being its running time.
Specialization (... is a kind of me.)
random searchGrover's algorithm, Czech, Havas, and Majewski's order-preserving minimal perfect hashing.
Note:
From Algorithms and Theory of Computation Handbook, 15-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC. A Monte Carlo algorithm gives more precise results the longer you run it. A Las Vegas algorithm always gives the right answer, but the run time is indeterminate.
Author: CRC-A
lattice
(definition)
Definition:
A point lattice generated by taking integer linear combinations of a set of basis vectors.
Note:
From Algorithms and Theory of Computation Handbook, page 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
layered graph
(definition)
Definition:
A connected graph where "layers" L0 ... Lk partition the vertices. Each edge, which has a nonnegative integral weight, connects only vertices in successive layers. The width is the greatest number of vertices in any layer, i.e., MAXi=0k |Li|.
Generalization (I am a kind of ...)
connected graph.
Specialization (... is a kind of me.)
bipartite graph.
Note:
A bipartite graph is a layered graph with two layers. A. Fiat, D.P. Foster, H.J. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan. Competitive Algorithms for Layered Graph Traversal. SIAM J. Comput., to appear. Preliminary version appeared in FOCS '91. Contributed by Giovanni Fiaschi <Giovanni.Fiaschi@marconi.com> June 2000.
Author: PEB
LCS
(classic problem)
Definition:
Either longest common subsequence or longest common substring.
Note:
The longest common substring is contiguous, while the longest common subsequence need not be.
Author: PEB
leaf
(definition)
Definition:
A node in a tree without any children.
Also known as external node, terminal node.
Aggregate parent (I am a part of or used in ...)
tree.
Note:
Every node in a tree is either a leaf or an internal node. The root may be a leaf.
Author: PEB
least common multiple
(definition)
Definition:
The least integer which is a multiple of given integers. For instance, LCM(6, 10) = 30.
Also known as LCM.
Author: PEB
leftist tree
(data structure)
Definition:
A priority queue implemented with a variant of a binary tree. Every node has a count which is the distance to the nearest leaf. In addition to the heap property, leftist trees are kept so the right descendant of each node has the shorter distance to a leaf.
Generalization (I am a kind of ...)
priority queue.
Aggregate child (... is a part of or used in me.)
binary tree, heap property.
Note:
These are called "leftist" because the left subtrees are usually taller than the right subtrees.
Author: PEB
left rotation
(algorithm)
Definition:
(1) In a binary search tree, pushing a node N down and to the left to balance the tree. N's right child replaces N, and the right child's left child becomes N's right child. (2) In an array, moving all items to the next lower location. The first item is moved to the last location, which is now vacant. (3) In a list, removing the head and inserting it at the tail.
Also known as rotate left.
Note:
Also known as left single rotation, in contrast to double left rotation.
Author: BB
Lempel-Ziv-Welch
(algorithm)
Definition:
A compression algorithm that codes strings of characters with codes of a fixed number of bits. Every new string in the input is added to a table until it is full. The codes of existing strings are output instead of the strings.
Also known as LZW compression.
Author: GS
More information
J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, May 1977. Terry Welch, A Technique for High-Performance Data Compression, Computer, June 1984.
level-order traversal
(algorithm)
Definition:
Process all nodes of a tree by depth: first the root, then the children of the root, etc. Equivalent to a breadth-first search from the root.
Note:
For instance, if the "processing" is just printing, a tree is printed as "root, all children of the root, all grandchildren (children of children) of the root, etc." Here is pseudocode for an inefficient level-order traversal of a binary tree:
levelorderAux(tree, level)
begin
if tree is null, return;
if level is 1, then
print(tree.root);
else if level greater than 1, then
levelorderAux(tree.left_subtree, level-1);
levelorderAux(tree.right_subtree, level-1);
endif
end
levelorder(tree)
begin
for d = 1 to height(tree)
levelorderAux(tree, d);
endfor
end See [Stand98, p. 251].
Author: PEB
Levenshtein distance
(definition)
Definition:
(1) The smallest number of insertions, deletions, and substitutions required to change one string or tree into another. (2) A Θ(m × n) algorithm to compute the distance between strings, where m and n are the lengths of the strings.
Also known as edit distance.
Generalization (I am a kind of ...)
string matching with errors.
Aggregate child (... is a part of or used in me.)
edit operation.
Note:
(1) From Algorithms and Theory of Computation Handbook, page 14-35, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
More information
Wikipedia entry which has links to implementations. March 2003 pictures of Levenshtein at a reception.
Vladimir I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Doklady Akademii Nauk SSSR, 163(4):845-848, 1965 (Russian). English translation in Soviet Physics Doklady, 10(8):707-710, 1966.
(Doklady is Russian for "Report". Sometimes transliterated in English as Doclady or Dokladi.)
lexicographical order
(definition)
Definition:
Alphabetical or "dictionary" order.
Note:
For instance, ordering cities by name rather than, say, by country or population (attributes of the named entity). The exact order, for example A-Za-z vs. aA-zZ etc., depends on the locale and application.
Author: PEB
linear
(definition)
Definition:
(1) Any function which is a constant times the argument plus a constant: f(x)=c1x + c0. (2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by a linear function of the problem size, n. More formally m(n) = O(n).
Note:
Strictly speaking, a linear function is polynomial with the highest exponent being 1. However polynomial usually means exponents greater than 1.
Author: PEB
linear congruential generator
(algorithm)
Definition:
A class of algorithms that are pseudo-random number generators. The next number is generated from the current one by rn+1 = (A × rn + B)mod M, where A and M are relatively prime numbers.
Note:
When implemented in software, A and B may be chosen so as to have integer overflow on nearly every step, and therefore have a less predictable sequence and avoid the mod operation. The low-order bits tend to be less random than high-order bits. This is improved by discarding some of the low-order bits. Therefore, the range of random numbers is less than the range of the integer used in the computation. Better algorithms are available, but they are more complex.
Author: BB
More information
Karl Entacher's thorough review and comparison of many linear congruential generators.
linear hash
(algorithm)
Definition:
A numeric function that maintains the order of input keys while changing their spacing.
Formal Definition: A hash function f for keys in S such that k1, k2 ∈ S ∧ k1 > k2 → f(k1) > f(k2).
Also known as order-preserving hash.
Generalization (I am a kind of ...)
hash function.
Specialization (... is a kind of me.)
order-preserving minimal perfect hashing.
Aggregate parent (I am a part of or used in ...)
grid file, hash heap.
Author: PEB
linear hashing
(data structure)
Definition:
A dynamic hashing table that grows one slot at a time. It has a family of hash functions, hi, where the range of hi+1 is twice the range of hi. Slots below a pointer, p, have been split. That is, key, k, is in slot hi(k) if hi(k) > p. Otherwise it is in hi+1(k). To maintain the load factor, slot p can be split (rehashed with hi+1) and p incremented. When p reaches the end, the ranges are doubled (i is incremented), and p starts over.
Also known as incremental hashing.
Generalization (I am a kind of ...)
dynamic hashing.
Note:
This is called incremental hashing in P. J. Plauger, "Hash It", ("STATE OF THE ART" column) Embedded Systems Programming, September 1998, 117-120. The article has a nearly complete implementation in C++. Stefan Edelkamp uses "incremental hashing" to mean a hash function where subsequent characters are independent.
Author: PEB
More information
W. Litwin, Linear hashing: A new tool for file and table addressing, Proc. 6th Conference on Very Large Databases, pages 212-223, 1980. Per-Åke Larson, Dynamic Hash Tables, CACM 31(4):446-457, April 1988.
linear probing
(data structure)
Definition:
A hash table in which a collision is resolved by putting the item in the next empty place in the array following the occupied place. Even with a moderate load factor, primary clustering tends to slow retrieval.
Aggregate parent (I am a part of or used in ...)
linear probing sort.
Note:
Deletion may be hard because finding collisions again relies on not creating empty spots. One solution is to mark an entry as deleted so it can be reused for insertion, but the search list is still intact.
Author: PEB
linear probing sort
(algorithm)
Definition:
Distribute each of n elements to one of m locations in an array (m>n) based on an interpolation of the element's key. In case of collisions, put the element in the next empty location. The array has extra space at the end for overflow. The second pass packs the elements back into an array of size n.
Generalization (I am a kind of ...)
distribution sort.
Aggregate child (... is a part of or used in me.)
linear probing.
Note:
The sort may fail if the overflow is exceeded. The distribution phase may be seen as putting the elements in a linear probing hash table using the interpolation function as the hash function.
Author: PEB
linear product
(definition)
Definition:
For two vectors X and Y, and with respect to two suitable operations  and  is a vector Z=Z0 Z1 ... Zm+n where Zk=i+j=kXi Yj (k=0, ... , m+n).
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
linear program
(definition)
Definition:
A problem expressible in the following form. Given an n × m real matrix A, m-vector b and n-vector c, determine minx{c· x | Ax ≥ b and x ≥ 0} where x ranges over all n-vectors and the inequalities are interpreted component-wise, i.e., x ≥ 0 means that the entries of x are nonnegative.
Note:
From Algorithms and Theory of Computation Handbook, page 34-18 (also pages 31-33 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
More information
Programación Lineal, a site in Spanish about linear programming.
linear quadtree
(data structure)
Definition:
A quadtree implemented as a single array of nodes.
Generalization (I am a kind of ...)
quadtree.
Author: PEB
linear search
(algorithm)
Definition:
Search an array or list by checking items one at a time.
Also known as sequential search.
Generalization (I am a kind of ...)
search.
Specialization (... is a kind of me.)
transpose sequential search.
Aggregate child (... is a part of or used in me.)
move-to-front heuristic.
Note:
Average run time is Θ (n/2) when the item is found.
Author: PEB
link
(definition)
Definition:
A reference, pointer, or access handle to another part of the data structure. Often, a memory address.
Author: PEB
linked list
(data structure)
Definition:
A list implemented by each item having a link to the next item.
Also known as singly linked list.
Specialization (... is a kind of me.)
doubly linked list, ordered linked list, circular list.
Note:
The first item, or head, is accessed from a fixed location, called a "head pointer." An ordinary linked list must be searched with a linear search. Average search time may be improved using a move-to-front heuristic or keeping it an ordered linked list. An external index, such as a hash table, inverted index, or auxiliary search tree may be used as a "cross index" to help find items quickly. A linked list can be used to implement other data structures, such as a queue, a stack, or a sparse matrix.
Author: PEB
More information
an introduction, a Java applet animation (Java).
list
(data structure)
Definition:
A collection of items accessible one after another beginning at the head and ending at the tail.
Generalization (I am a kind of ...)
bag.
Specialization (... is a kind of me.)
linked list, doubly linked list, circular list, self-organizing list, ordered linked list.
Aggregate parent (I am a part of or used in ...)
orthogonal lists.
Note:
A list may have additional access methods. A list may be ordered. A list can be seen as an ordered bag. A list may be kept as the leading items of an array, but inserting items other than at the end takes time.
Author: PEB
list contraction
(definition)
Definition:
Contracting a list by removing some of the items.
Note:
From Algorithms and Theory of Computation Handbook, page 47-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
little-o notation
(definition)
Definition:
A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = o(g(n)) means f(n) becomes insignificant relative to g(n) as n approaches infinity. The notation is read, "f of n is little oh of g of n".
Formal Definition: f(n) = o(g(n)) means for all c > 0 there exists some k > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ k. The value of k must not depend on n, but may depend on c.
Generalization (I am a kind of ...)
big-O notation.
Note:
As an example, 3n + 4 is o(n²) since for any c we can choose k > (3+ √(9+16c))/2c. 3n + 4 is not o(n). o(f(n)) is an upper bound, but is not an asymptotically tight bound.
Strictly, the character is the lower-case Greek letter omicron.
Author: PEB
More information
Little o is a Landau Symbol.
Lm distance
(definition)
Definition:
The generalized distance between two points. In a plane with point p1 at (x1, y1) and p2 at (x2, y2), it is (|x1 - x2|m + |y1 - y2|m)1/m.
Also known as Minkowski distance.
Note:
This is easily generalized to higher dimensions. Euclidean distance is L2 distance. Rectilinear, Manhattan or Hamming distance is L1 distance. L∞ distance is max(|x1 - x2|, |y1 - y2|). Adapted from [CLR90, page 912].
Author: PEB
More information
More formal definitions of distance measures. Wikipedia definition of distance in the mathematical or physical sense.
load factor
(definition)
Definition:
The number of elements in a hash table divided by the number of slots. Usually written α (alpha).
Note:
The higher the load factor, the slower the retrieval. With open addressing, the load factor cannot exceed 1. With chaining, the load factor often exceeds 1. After [CLR90, page 224].
Author: PEB
local alignment
(definition)
Definition:
The detection of local similarities among two or more strings.
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
locality-sensitive hashing
(algorithm)
Definition:
A probabilistic algorithm to quickly find points in a high dimensional space near a query point. Preprocessing: put every point in multiple hash tables. Each table has its own locality-sensitive hash function and uses buckets (or chaining) since many collisions are expected. The hash functions come from a family of functions. Finding: look up the query point in each hash table, and compute the distance from the query point of every point in the bucket.
Generalization (I am a kind of ...)
point access method.
Aggregate child (... is a part of or used in me.)
hash function, bucket.
Note:
This algorithm is for high dimensional spaces. For instance, a 1000 x 1000 image can be characterized by a vector in 1,000,000-dimensional space, one dimension for each pixel. To understand the algorithm, let the "hash functions" be random sets of the coordinates. If many coordinates of a point match the query point, it is likely to be close to the query point, at least closer than those that don't match.
Author: PEB
More information
Alexandr Andoni's Locality-Sensitive Hashing home page. Locality sensitive hashing in Wikipedia.
Alexandr Andoni and Piotr Indyk, Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions, CACM, 51(1):117-122, January 2008.
local optimum
(definition)
Definition:
A solution to a problem that is better than all other solutions that are slightly different, but worse than the global optimum.
Note:
Some search methods may get trapped in a local optimum and miss the global optimum.
Author: PEB
logarithmic
(definition)
Definition:
(1) Any function that is a constant times the logarithm of the argument: f(x)=c log x. (2) In complexity theory, when the measure of computation, m(n) (usually execution time or memory space), is bounded by a logarithmic function of the problem size, n. More formally m(n) = O(log n). (3) Sometimes imprecisely used to mean polylogarithmic.
Generalization (I am a kind of ...)
sublinear time algorithm.
Author: PEB
longest common subsequence
(classic problem)
Definition:
The problem of finding a maximum length (or maximum weight) subsequence of two or more strings.
Also known as heaviest common subsequence.
Note:
The longest common substring is contiguous, while the longest common subsequence need not be. 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
More information
Dan Hirschberg's pseudocode as an example of dynamic programming. Longest-common subsequence problem in Wikipedia.
longest common substring
(classic problem)
Definition:
Find the longest substring of two or more strings.
Note:
The longest common substring is contiguous, while the longest common subsequence need not be.
Author: PEB
More information
Dan Hirschberg's pseudocode as an example of dynamic programming.
Lotka's law
(definition)
Definition:
The number of authors making n contributions is about 1/na of those making one contribution, where a is often nearly 2.
Note:
A power law; often nearly an inverse square law. Contributed by Christiane Fritze <h0444who@rz.hu-berlin.de> July 2000.
Author: PEB
More information
A short biography of Alfred James Lotka.
Alfred J. Lotka, The Frequency Distribution of Scientific Productivity, Journal of the Washington Academy of Sciences, 16(12):317-323, 1926.
lower bound
(definition)
Definition:
A function or growth rate below which solving a problem is impossible.
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
lower triangular matrix
(data structure)
Definition:
A matrix that is only defined at (i,j) when i ≥ j.
Generalization (I am a kind of ...)
matrix.
Specialization (... is a kind of me.)
strictly lower triangular matrix.
Note:
For example It may be more compactly represented in an array by storing entry (i,j) in location i(i-1)/2 + j (one-based indexing).
Author: PEB
lowest common ancestor
(definition)
Definition:
The deepest node in a tree that is an ancestor of two given leaves.
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
l-reduction
(definition)
Definition:
A Karp reduction that preserves approximation properties of optimization problems.
Note:
From Algorithms and Theory of Computation Handbook, page 29-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
lucky sort
(algorithm)
Definition:
The best possible sort algorithm: it is so lucky that the input is already sorted, and it need do nothing!
Note:
Defined more for humorous, rather than serious, purposes. Time complexity is Θ(0) (zero): it takes no time.
Author: PEB
Published - April 2009
Find free glossaries at TranslationDirectory.com
Find free dictionaries at TranslationDirectory.com
Subscribe to free TranslationDirectory.com newsletter
Need more translation jobs from translation agencies? Click here!
Translation agencies are welcome to register here - Free!
Freelance translators are welcome to register here - Free!
Submit your glossary or dictionary for publishing at TranslationDirectory.com
|
